Digging for data structures
Anthony Cozzie, Frank Stratton, Hui Xue, Samuel Talmadge King · 2008
Because writing computer programs is hard, computer programmers are taught to use encapsulation and mod-ularity to hide complexity and reduce the potential for errors. Their programs will have a high-level, hierar-chical structure that reflects their choice of internal ab-stractions. We designed and forged a system, Laika, that detects this structure in memory using Bayesian unsu-pervised learning. Because almost all programs use data structures, their memory images consist of many copies of a relatively small number of templates. Given a mem-ory image, Laika can find both the data structures and their instantiations. We then used Laika to detect three common polymor-phic botnets by comparing their data structures. Because it avoids their code polymorphism entirely, Laika is ex-tremely accurate. Finally, we argue that writing a data structure polymorphic virus is likely to be considerably harder than writing a code polymorphic virus. 1