On callgraphs and generative mechanisms

Springer Science and Business Media LLC - Tập 3 - Trang 299-310 - 2007
Daniel Bilar1
1Department of Computer Science, Wellesley College, Wellesley, USA

Tóm tắt

This paper examines the structural features of callgraphs. The sample consisted of 120 malicious and 280 non-malicious executables. Pareto models were fitted to indegree, outdegree and basic block count distribution, and a statistically significant difference shown for the derived power law exponent. A two-step optimization process involving human designers and code compilers is proposed to account for these structural features of executables.

Tài liệu tham khảo

Adamic L. and Huberman B. (2002). Zipf’s law and the internet. Glottometrics 3: 143–150 Alexander S. (2005). Defeating compiler-level buffer overflow protection.. j-LOGIN 30(3): 59–71 Barabasi A.L. (1999). Mean field theory for scale-free random networks. Phys. A Stat. Mech. Appl. 272: 173–187 cond-mat/9907068 Bilar, D.: Fingerprinting malicious code through statistical opcode analysis. In: ICGeS ’07: Proceedings of the 3rd International Conference on Global E-Security, London (UK) (2007) Carlson J.M. and Doyle J. (1999). Highly optimized tolerance: A mechanism for power laws in designed systems. Phys. Rev. E 60(2): 1412 Carlson J.M. and Doyle J. (2002). Complexity and robustness. Proc. Natl. Acad. Sci. 99(Suppl 1): 2538–2545 Chatzigeorgiou, A., Tsantalis, N., Stephanides, G.: Application of graph theory to OO software engineering. In WISER ’06: Proceedings of the 2006 International Workshop on Workshop on Interdisciplinary Software Engineering Research, pp. 29–36, New York, NY, USA. ACM Press, New York (2006) Christodorescu, M., Jha, S.: Static analysis of executables to detect malicious patterns. In Security ’03: Proceedings of the 12th USENIX Security Symposium, pp. 169–186. USENIX Association, USENIX Association (2003) Clementi, A.: Anti-virus comparative no. 11. Technical report, Kompetenzzentrum IT, Insbruck (Austria). http://www.av-comparatives.org/seiten/ergebnisse/report11.pdf (2006) Cowan, C., Pu, C., Maier, D., Walpole, J., Bakke, P., Beattie, S., Grier, A., Wagle, P., Zhang, Q., Hinton, H.: StackGuard: Automatic adaptive detection and prevention of buffer-overflow attacks. In: Proceedings of 7th USENIX Security Conference, pp. 63–78, San Antonio, Texas (1998) Doyle J. and Carlson J.M. (2000). Power laws, highly optimized tolerance and generalized source coding. Phys. Rev. Lett. 84(24): 5656–5659 Doyle J.C., Alderson D.L., Li L., Low S., Roughan M., Shalunov S., Tanaka R. and Willinger W. (2005). The “robust yet fragile” nature of the Internet. Proc. Natl. Acad. Sci. 102(41): 14497–14502 Dullien, T.: Binnavi v1.2. http://www.sabre-security.com/products/binnavi.html (2006) Dullien, T., Rolles, R.: Graph-based comparison of executable objects. In SSTIC ’05: Symposium sur la Sécurité des Technologies de l’Information et des Communications. Rennes, France (2005) Ekeland I. (2006). The Best of All Possible Worlds: Mathematics and Destiny. University of Chicago Press, Chicago Fan, Z.: Estimation problems for distributions with heavy tails. PhD thesis, Georg-August-Universität zu Göttingen (2001) Filiol É. (2007). Metamorphism, formal grammars and undecidable code mutation. Int. J. Comput. Sci. 2(2): 70–75 Flake, H.: Compare, Port, Navigate. Black Hat Europe 2005 Briefings and Training (2005) Foster J.C., Osipov V., Bhalla N. and Heinen N. (2005). Buffer Overflow Attacks. Syngress, Rockland, USA Gamma E., Helm R., Johnson R. and Vlissides J. (1993). Design patterns: Abstraction and reuse of object-oriented design. Lect. Notes Comput. Sci. 707: 406–431 Goldstein M.L., Morris S.A. and Yen G.G. (2004). Problems with fitting to the power-law distribution. Eur. J. Phys. B 41(2): 255–258 cond-mat/0402322 Guilfanov, I.: Ida pro v5.0.0.879. http://www.datarescue.com/idabase/ (2006) Haneda, M., Knijnenburg, P.M.W., Wijshoff, H.A.G.: Optimizing general purpose compiler optimization. In: CF ’05: Proceedings of the 2nd Conference on Computing Frontiers, pp. 180–188, New York, NY, USA. ACM Press, New York (2005) herm1t. VX Heaven. http://vx.netlux.org// (2007) Kirchner J.W. (1993). Statistical inevitability of horton’s laws and the apparent randomness of stream channel networks. Geology 21: 591–594 Knuth D.E. (1976). Big omicron and big omega and big theta. SIGACT News 8(2): 18–24 Krügel C., Kirda E., Mutz D., Robertson W. and Vigna G. (2005). Polymorphic worm detection using structural information of executables. In: Valdes, A. and Zamboni, D. (eds) Recent Advances in Intrusion Detection, vol. 3858 of Lecture Notes in Computer Science, pp 207–226. Springer, Heidelberg Lakos J. (1996). Large-scale C++ software design. Addison Wesley Longman Publishing Co., Inc, Redwood City Li, L., Alderson, D., Willinger, W., Doyle, J.: A first-principles approach to understanding the internet’s router-level topology. In: SIGCOMM ’04: Proceedings of the 2004 Conference on Applications, Technologies, Architectures, and Protocols for Computer Communications, pp. 3–14, New York, NY, USA. ACM Press, New York (2004) Li, W.-J., Wang, K., Stolfo, S., Herzog, B.: Fileprints: Identifying file types by n-gram analysis. In SMC ’05: Proceedings from the Sixth Annual IEEE Information Assurance Workshop on Systems, Man and Cybernetics, pp. 64– 71. West Point, New York (2005) Limpert E., Stahel W.A. and Abbt M. (2001). Log-normal distributions across the sciences: keys and clues. BioScience 51(5): 341–352 Manning M., Carlson J.M. and Doyle J. (2005). Highly optimized tolerance and power laws in dense and sparse resource regimes. Phys. Rev. E (Stat. Nonlinear Soft Matter Phys.) 72(1): 016108–016125 physics/0504136 Miller, B.P., Cooksey, G., Moore, F.: An empirical study of the robustness of macos applications using random testing. In: RT ’06: Proceedings of the 1st International workshop on Random Testing, pp. 46–54, New York, NY, USA. ACM Press, New York (2006) Miller B.P., Fredriksen L. and So B. (1990). An empirical study of the reliability of unix utilities. Commun. ACM 33(12): 32–44 Milo R., Shen-Orr S., Itzkovitz S., Kashtan N., Chklovskii D. and Alon U. (2002). Network Motifs: Simple Building Blocks of Complex Networks. Science 298(5594): 824–827 Mina Guirguis, A.B., Matta, I.: Reduction of quality (roq) attacks on dynamic load balancers: Vulnerability assessment and design tradeoffs. In: Infocom ’07: Proceedings of the 26th IEEE International Conference on Computer Communication, Anchorage (AK) (2007, to appear) Mina Guirguis, I.M., Bestavros, A., Zhang, Y.: Adversarial exploits of end-systems adaptation dynamics. J. Parallel Distrib. Comput. (2007, to appear) Mitzenmacher M. (2004). Dynamic models for file sizes and double pareto distributions. Internet Math. 1(3): 305–334 Muchnick S.S. (1998). Advanced compiler design and implementation. Morgan Kaufmann Publishers Inc, San Francisco, pp 326–327 ISBN 1-55860-320-4 Myers C. (2003). Software systems as complex networks: Structure, function and evolvability of software collaboration graphs. Phys. Rev. E (Stat. Nonlinear Soft Matter Phys.) 68(4): 046116 Newman M. (2005). Power laws, Pareto distributions and Zipf’s law. Contemp. Phys. 46(5): 323–351 Newman M., Barabasi A.-L. and Watts D.J. (2006). The Structure and Dynamics of Networks: (Princeton Studies in Complexity). Princeton University Press, Princeton Newman M.E.J. (2003). The structure and function of complex networks. SIAM Rev. 45: 167 Potanin A., Noble J., Frean M. and Biddle R. (2005). Scale-free geometry in oo programs. Commun. ACM 48(5): 99–103 Pržulj, N.: Biological network comparison using graphlet degree distribution. In: Proceedings of the 2006 European Conference on Computational Biology, ECCB ’06, Oxford, UK. Oxford University Press, New York (2006) Resnick S. (1997). Heavy tail modeling and teletraffic data. Ann. Stat. 25(5): 1805–1869 Schneider E.D. and Sagan D. (2005). Into the Cool : Energy Flow, Thermodynamics and Life. University Of Chicago Press, Chicago Skoudis E. and Zeltser L. (2003). Malware: Fighting Malicious Code. Prentice Hall PTR, Upper Saddle River Szor P. (2005). The Art of Computer Virus Research and Defense. Prentice Hall PTR, Upper Saddle River, 252–293 Szor P. (2005). The Art of Computer Virus Research and Defense. Addison-Wesley Professional, Upper Saddle River (NJ) Szor, P., Ferrie, P.: Hunting for metamorphic. In: VB ’01: Proceedings of the 11th Virus Bulletin Conference (2001) Valverde S., Ferrer Cancho R. and Solé R.V. (2002). Scale-free networks from optimal design. Europhys. Lett. 60: 512–517 cond-mat/0204344 Valverde S. and Sole R.V. (2005). Logarithmic growth dynamics in software networks. Europhys. Lett. 72: 5–12 physics/0511064 Weber, M., Schmid, M., Schatz, M., Geyer, D.: A toolkit for detecting and analyzing malicious software. In: ACSAC ’02: Proceedings of the 18th Annual Computer Security Applications Conference, Washington (DC) (2002) Whittaker J. and Thompson H. (2003). How to break Software security. Addison Wesley (Pearson Education), Reading Willinger, W., Alderson, D., Doyle, J.C., Li, L.: More normal than normal: scaling distributions and complex systems. In: WSC ’04: Proceedings of the 36th Conference on Winter Simulation, pp. 130–141. Winter Simulation Conference (2004) Wu G.T., Twomey S.L. and Thiers R.E. (1975). Statistical evaluation of method-comparison data. Clin. Chem. 21(3): 315–320