More Web Proxy on the site http://driver.im/

Article

Digging for data structures

Authors:

Anthony Cozzie,

Frank Stratton,

Samuel T. KingAuthors Info & Claims

OSDI'08: Proceedings of the 8th USENIX conference on Operating systems design and implementation

Pages 255 - 266

Published: 08 December 2008 Publication History

Abstract

Because writing computer programs is hard, computer programmers are taught to use encapsulation and modularity to hide complexity and reduce the potential for errors. Their programs will have a high-level, hierarchical structure that reflects their choice of internal abstractions. We designed and forged a system, Laika, that detects this structure in memory using Bayesian unsupervised learning. Because almost all programs use data structures, their memory images consist of many copies of a relatively small number of templates. Given a memory image, Laika can find both the data structures and their instantiations.

We then used Laika to detect three common polymorphic botnets by comparing their data structures. Because it avoids their code polymorphism entirely, Laika is extremely accurate. Finally, we argue that writing a data structure polymorphic virus is likely to be considerably harder than writing a code polymorphic virus.

References

[1]

2007 malware report: The economic impact of viruses, spyware, adware, botnets, and other malicious code. http://www.computereconomics.com/ page.cfm?name=Malware%20Report.

[2]

Clamav website. http://www.clamav.org.

[3]

BALAKRISHNAN, G., AND REPS, T. Analyzing memory accesses in x86 executables. In In Comp. Construct (2004), Springer-Verlag, pp. 5-23.

[4]

BHATKAR, S., SEKAR, R., AND DUVARNEY, D. C. Efficient techniques for comprehensive protection from memory error exploits. In Proceedings of the 14th USENIX Security Symposium (Aug. 2005), USENIX.

Digital Library

[5]

BRUSCHI, D., MARIGNONI, L., AND MONGA, M. Detecting self-mutating malware using control flow graph matching. Technical Report, Universitaa degli Studi di Milano, http://idea.sec.dico.unimi.it/lorenzo/rt0906.pdf.

[6]

CHEN, P. M., AND NOBLE, B. D. When virtual is better than real. In HotOS (2001), IEEE Computer Society, pp. 133-138.

[7]

CHESS, D. M., AND WHITE, S. R. An undetectable computer virus. In Proceedings of the 2000 Virus Bulletin Conference (2000).

[8]

CHRISTODORESCU, M., JHA, S., SESHIA, S. A., SONG, D., AND BRYANT, R. E. Semantics-aware malware detection. In Proceedings of the 2005 IEEE Symposium on Security and Privacy (Oakland 2005) (Oakland, CA, USA, may 2005), pp. 32-46.

Digital Library

[9]

COHEN, F. Computer viruses: Theory and experiments. In Computers and Security (1987), pp. 22-35.

Digital Library

[10]

CORBETT, J. C. Using shape analysis to reduce finite-state models of concurrent java programs. ACM Trans. Softw. Eng. Methodol. 9, 1 (2000), 51-93.

Digital Library

[11]

DENNING, D. E. An intrusion-detection model. IEEE Trans. Softw. Eng. 13, 2 (February 1987), 222-232.

Digital Library

[12]

FRANKLIN, J., PAXSON, V., PERRIG, A., AND SAVAGE, S. An inquiry into the nature and causes of the wealth of internet miscreants. In CCS '07: Proceedings of the 14th ACM conference on Computer and communications security (New York, NY, USA, 2007), ACM, pp. 375-388.

Digital Library

[13]

GARFINKEL, T., AND ROSENBLUM, M. A virtual machine introspection based architecture for intrusion detection. In NDSS (2003), The Internet Society.

[14]

GHIYA, R., AND HENDREN, L. J. Is it a tree, a dag, or a cyclic graph? a shape analysis for heap-directed pointers in c. In POPL '96: Proceedings of the 23rd ACM SIGPLAN-SIGACT symposium on Principles of programming languages (New York, NY, USA, 1996), ACM, pp. 1-15.

Digital Library

[15]

GOODIN, D. Move over storm - there's a bigger, stealthier botnet in town. http://www.theregister.co.uk/2008/04/07/ kraken_botnet_menace/.

[16]

GORDON, J. Lessons from virus developers: The beagle worm history through april 24, 2005. In Security Focus Guest Feature Forum (2004).

[17]

HSI, I., POTTS, C., AND MOORE, M. Ontological excavation: Unearthing the core concepts of applications. In Proceedings of the 10th Working Conference on Reverse Engineering (WCRE) (2003).

Digital Library

[18]

JONES, S. T., ARPACI-DUSSEAU, A. C., AND ARPACIDUSSEAU, R. H. Antfarm: Tracking processes in a virtual machine environment. In Proceedings of the 2006 USENIX Annual Technical Conference: May 30-June 3, 2006, Boston, MA, USA (2006).

Digital Library

[19]

JONES, S. T., ARPACI-DUSSEAU, A. C., AND ARPACIDUSSEAU, R. H. Geiger: monitoring the buffer cache in a virtual machine environment. In ASPLOS-XII: Proceedings of the 12th international conference on Architectural support for programming languages and operating systems (New York, NY, USA, 2006), ACM Press, pp. 14-24.

Digital Library

[20]

JONES, S. T., ARPACI-DUSSEAU, A. C., AND ARPACIDUSSEAU, R. H. Vmm-based hidden process detection and identification using lycosid. In VEE '08: Proceedings of the fourth ACM SIGPLAN/SIGOPS international conference on Virtual execution environments (New York, NY, USA, 2008), ACM, pp. 91-100.

Digital Library

[21]

JORDAN, M. Dealing with metamorphism, October 2002.

[22]

JOSHI, A., KING, S. T., DUNLAP, G. W., AND CHEN, P. M. Detecting past and present intrusions through vulnerability-specific predicates. In Proceedings of the 2005 Symposium on Operating Systems Principles (SOSP) (October 2005), pp. 91-104.

Digital Library

[23]

KRUEGEL, C., KIRDA, E., MUTZ, D., ROBERTSON, W., AND VIGNA, G. Polymorphic worm detection using structural information of executables, 2005.

[24]

KRUEGEL, C., ROBERTSON, W., AND VIGNA, G. Detecting Kernel-Level Rootkits Through Binary Analysis. In Proceedings of the Annual Computer Security Applications Conference (ACSAC) (Tucson, AZ, December 2004), pp. 91-100.

Digital Library

[25]

LINN, C., AND DEBRAY, S. Obfuscation of executable code to improve resistance to static disassembly.

[26]

MA, J., DUNAGAN, J., WANG, H. J., SAVAGE, S., AND VOELKER, G. M. Finding diversity in remote code injection exploits. In IMC '06: Proceedings of the 6th ACM SIGCOMM conference on Internet measurement (New York, NY, USA, 2006), ACM, pp. 53-64.

Digital Library

[27]

MÜLLER, H. A., ORGUN, M. A., TILLEY, S. R., AND UHL, J. S. A reverse engineering approach to subsystem structure identification. Journal of Software Maintenance: Research and Practice 5(4) (December 1993), 181-204.

[28]

NUGENT, J., ARPACI-DUSSEAU, A. C., AND ARPACIDUSSEAU, R. H. Controlling your place in the file system with gray-box techniques. In Proceedings of the 2003 USENIX Annual Technical Conference (June 2003).

[29]

PETRONI, N. L., FRASER, T., MOLINA, J., AND ARBAUGH, W. A. Copilot-a Coprocessor-based Kernel Runtime Integrity Monitor. In Proceedings of the 2004 USENIX Security Symposium (August 2004).

Digital Library

[30]

SINGH, P. K., AND LAKHOTIA, A. Analysis and detection of computer viruses and worms: An annotated bibliography. In ACM SIGPLAN Notices (2002), pp. 29-35.

Digital Library

[31]

SIVATHANU, M., PRABHAKARAN, V., POPOVICI, F., DENEHY, T. E., ARPACI-DUSSEAU, A. C., AND ARPACI-DUSSEAU, R. H. Semantically-Smart Disk Systems. In Proceedings of the Second USENIX Symposium on File and Storage Technologies (FAST '03) (San Francisco, CA, March 2003), pp. 73-88.

Digital Library

[32]

STEENSGAARD, B. Points-to analysis by type inference of programs with structures and union. In Proceedings of the 6th International Conference on Compiler Construction (1996), pp. 136-150.

Digital Library

[33]

SUTTON, A., AND MALETIC, J. Mappings for accurately reverse engineering uml class models from c++. In Proceedings of the 12th Working Conference on Reverse Engineering (WCRE) (2005).

Digital Library

[34]

WONG, K., TILLEY, S. R., MÜLLER, H. A., AND STOREY, M.- A. D. Structural redocumentation: A case study. IEEE Software 12, 1 (1995), 46-54.

Digital Library

Cited By

Oliveri ABalzarotti D(2022)In the Land of MMUs: Multiarchitecture OS-Agnostic Virtual Memory ForensicsACM Transactions on Privacy and Security10.1145/352810225:4(1-32)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3528102
Pagani FBalzarotti DHeninger NTraynor P(2019)Back to the whiteboardProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361460(1751-1768)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361460
Wang HXie XLin SLin YLi YQin SLiu YLiu TDumas MPfahl DApel SRusso A(2019)Locating vulnerabilities in binaries via memory layout recoveringProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338966(718-728)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338966
Show More Cited By

Recommendations

Robust signatures for kernel data structures
CCS '09: Proceedings of the 16th ACM conference on Computer and communications security

Kernel-mode rootkits hide objects such as processes and threads using a technique known as Direct Kernel Object Manipulation (DKOM). Many forensic analysis tools attempt to detect these hidden objects by scanning kernel memory with handmade signatures; ...
Digging For Worms, Fishing For Answers
ACSAC '02: Proceedings of the 18th Annual Computer Security Applications Conference

Worms continue to be a leading security threat on the Internet.This paper analyzes several of the more widespreadworms and develops a general life-cycle for them. The life-cycle,from the point of view of the victim host, consistsof four stages: target ...
Concurrent Data Structures for Near-Memory Computing
SPAA '17: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures

The performance gap between memory and CPU has grown exponentially. To bridge this gap, hardware architects have proposed near-memory computing (also called processing-in-memory, or PIM), where a lightweight processor (called a PIM core) is located ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

OSDI'08: Proceedings of the 8th USENIX conference on Operating systems design and implementation

December 2008

384 pages

Sponsors

USENIX Assoc: USENIX Assoc

In-Cooperation

SIGOPS: ACM Special Interest Group on Operating Systems

Publisher

USENIX Association

United States

Publication History

Published: 08 December 2008

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

39
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 05 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Oliveri ABalzarotti D(2022)In the Land of MMUs: Multiarchitecture OS-Agnostic Virtual Memory ForensicsACM Transactions on Privacy and Security10.1145/352810225:4(1-32)Online publication date: 9-Jul-2022
https://dl.acm.org/doi/10.1145/3528102
Pagani FBalzarotti DHeninger NTraynor P(2019)Back to the whiteboardProceedings of the 28th USENIX Conference on Security Symposium10.5555/3361338.3361460(1751-1768)Online publication date: 14-Aug-2019
https://dl.acm.org/doi/10.5555/3361338.3361460
Wang HXie XLin SLin YLi YQin SLiu YLiu TDumas MPfahl DApel SRusso A(2019)Locating vulnerabilities in binaries via memory layout recoveringProceedings of the 2019 27th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3338906.3338966(718-728)Online publication date: 12-Aug-2019
https://dl.acm.org/doi/10.1145/3338906.3338966
Erinfolami RPrakash AGalbraith SRussello GSusilo WGollmann DKirda ELiang Z(2019)DeClassifierProceedings of the 2019 ACM Asia Conference on Computer and Communications Security10.1145/3321705.3329833(28-40)Online publication date: 2-Jul-2019
https://dl.acm.org/doi/10.1145/3321705.3329833
Jindal AHu YArpaci-Dusseau AVoelker G(2018)Differential energy profilingProceedings of the 13th USENIX conference on Operating Systems Design and Implementation10.5555/3291168.3291206(511-526)Online publication date: 8-Oct-2018
https://dl.acm.org/doi/10.5555/3291168.3291206
Kate SOre JZhang XElbaum SXu ZLeavens GGarcia APăsăreanu C(2018)Phys: probabilistic physical unit assignment and inconsistency detectionProceedings of the 2018 26th ACM Joint Meeting on European Software Engineering Conference and Symposium on the Foundations of Software Engineering10.1145/3236024.3236035(563-573)Online publication date: 26-Oct-2018
https://dl.acm.org/doi/10.1145/3236024.3236035
Rupprecht TChen XWhite DBoockmann JLüttgen GBos HRosu GDi Penta MNguyen T(2017)DSIbin: identifying dynamic data structures in C/C++ binariesProceedings of the 32nd IEEE/ACM International Conference on Automated Software Engineering10.5555/3155562.3155607(331-341)Online publication date: 30-Oct-2017
https://dl.acm.org/doi/10.5555/3155562.3155607
Escalada JOrtin FScully T(2017)An Efficient Platform for the Automatic Extraction of Patterns in Native CodeScientific Programming10.1155/2017/32738912017(3)Online publication date: 1-Feb-2017
https://dl.acm.org/doi/10.1155/2017/3273891
Padhye RSen KUchitel SOrso ARobillard M(2017)TravioliProceedings of the 39th International Conference on Software Engineering10.1109/ICSE.2017.50(473-483)Online publication date: 20-May-2017
https://dl.acm.org/doi/10.1109/ICSE.2017.50
Sun PHan RZhang MZonouz SSchwab SRobertson WBalzarotti D(2016)Trace-free memory data structure forensics via past inference and future speculationsProceedings of the 32nd Annual Conference on Computer Security Applications10.1145/2991079.2991118(570-582)Online publication date: 5-Dec-2016
https://dl.acm.org/doi/10.1145/2991079.2991118
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents