Appilicability of Theoritical Computer Science in Malware research I would like to know the importance of TCS in Malware research. Due to the large volume of new malware variants received per day (~50,000 samples/day according to McAfee), malware researchers are heavily dependent on dynamic analysis (i.e. running the samples in a sandbox and monitoring their behavior) and moving away from static analysis and Reverse engineering as these approaches are very time consuming and sometimes becomes very challenging due to  obfuscation/encryption. 

I found a very useful talk (BlackHat 2010) by Greg Hoglund on Malware attribution where the speaker talks about the importance of bringing in the malware authors and their networks into the picture which gives valuable information than just analyzing the binary itself.

I have two questions:


If malware researchers move towards analyzing the behavior of malware authors and their network, in the future does TCS has any importance in malware research.  
As I am not strong in TCS, I would like to know where exactly TCS fits
in malware research.


Thank you.
Fred Cohen is an authority &amp; early researcher on the theory of computer viruses.  see that wikipedia page for references. his 1987 paper is given credit as maybe the 1st analogy of the virus checking problem to the halting problem. 

the basic idea is to create a program X that calls a virus checking subroutine with a program code as parameter. then, if the subroutine returns "is a virus", exit. if it returns "is not a virus", infect the system. such a program cannot exist by diagonalization/contradiction, passing its own code as the parameter. therefore there is no perfect virus checker. 

but it would seem an easy counterargument to this statement could be, program X contains a harmful section of code, and that its irrelevant whether it is called or not-- the program is potentially harmful if it contains any "harmful section of code".

as I recall this result was published separately in a mathematical journal but cant find the reference right now.

a more recent/advanced topic is detecting polymorphic viruses that change their code in equivalent but random ways.

another promising approach that seems to avoid the halting problem issue (in a way that demonstrates abstract theoretical "no-go theorems" can be misleading or even inapplicable in practice) is to create a secure "sandbox" in which a program can run but cannot do anything harmful.

the modern web browser can be seen as an attempt to build such a system. the complexity of securing it arises mainly with Javascript.

Google is building the NaCL[3] framework that partly originated in academia and is the current leading contender for a high functional sandbox system integrated into the modern browser that still allows machine code. a provably secure software checker validates candidate programs. there are recent dramatic improvements announced[4].

a novel recent idea is to use graph based analysis of execution traces[5].

a more recent topic of virtualization has various security implications/applications as you note eg virus vendors building virtualization systems to find/detect viruses etc.[6]

the sophistication of the recent stuxnet virus, apparently the worlds 1st state/govt-sponsored, military-agency-developed virus for cyber/espionage/sabotage purposes, has led to serious/heavy academic study, see the extensive references on wikipedia. there is a recent/new variant discovered targeting the financial industry called flame.

[1] An Undetectable Computer Virus David M. Chess and Steve R. White

[2] Trends in computer virus research Cohen, 1991

[3] Native Client: A Sandbox for Portable, Untrusted x86 Native Code by Yee et al 2009

[4] NaCl to give way to RockSalt: Computer scientists develop a tool to improve software fault isolation 2012

[5] Graph-based malware detection using dynamic analysis by Anderson et al

[6] Detection of Metamorphic and Virtualization-based
Malware using Algebraic Specification by Webster, Malcolm