Mihai's Papers & Talks


These are the papers I have written and (maybe) published, as well as the talks I have given.
Paper: Anomaly Detection as a Reputation System for Online Auctioning
November 10, 2005
Abstract: display hide
Existing reputation systems used by online auction houses do not address the concern of a buyer shopping for commodities---finding a good bargain. These systems do not provide information on the practices adopted by sellers to ensure profitable auctions. These practices may be legitimate, like imposing a minimum starting bid on an auction, or fraudulent, like using colluding bidders to inflate the final price in a practice known as shilling.
We develop a reputation system to help buyers identify sellers whose auctions seem price-inflated. Our reputation system is based upon models that characterize sellers according to statistical metrics related to price inflation. We combine the statistical models with anomaly detection techniques to identify the set of suspicious sellers. The output of our reputation system is a set of values for each seller representing the confidence with which the system can say that the auctions of the seller are price-inflated.
We evaluate our reputation system on 604 high-volume sellers who posted 37,525 auctions on eBay. Our system automatically pinpoints sellers whose auctions contain potential shill bidders. When we manually analyze these sellers' auctions, we find that many winning bids are at about the items' market values, thus undercutting a buyer's ability to find a bargain and demonstrating the effectiveness of our reputation system.
Published in the Proceedings of the 12th ACM Conference on Computer and Communications Security (CCS'05) , November 7-11, 2005, Alexandria, VA, USA .
Paper: String Analysis for x86 Binaries
Mihai Christodorescu, Nicholas Kidd, Wen-Han Goh
September 6, 2005
Abstract: display hide
Information about string values at key points in a program can help program understanding, reverse engineering, and forensics. We present a static-analysis technique for recovering possible string values in an executable program, when no debug information or source code is available. The result of our analysis is a regular language that describes a superset of the string values possible at a given program point. We also impart some of the lessons learned in the process of implementing our analysis as a tool for recovering C-style strings in x86 executables.
Published in the Proceedings of the 6th ACM SIGPLAN-SIGSOFT Workshop on Program Analysis for Software Tools and Engineering (PASTE 2005), September 5-6, 2005, Lisbon, Portugal .
Paper: Semantics-Aware Malware Detection
Mihai Christodorescu, Somesh Jha, Sanjit A. Seshia, Dawn Song, Randal E. Bryant
May 9, 2005
Abstract: display hide
A malware detector is a system that attempts to determine whether a program has malicious intent. In order to evade detection, malware writers (hackers) frequently use obfuscation to morph malware. Malware detectors that use a pattern-matching approach (such as commercial virus scanners) are susceptible to obfuscations used by hackers. The fundamental deficiency in the pattern-matching approach to malware detection is that it is purely syntactic and ignores the semantics of instructions. In this paper, we present a malware-detection algorithm that addresses this deficiency by incorporating instruction semantics to detect malicious program traits. Experimental evaluation demonstrates that our malware-detection algorithm can detect variants of malware with a relatively low run-time overhead. Moreover, our semantics-aware malware detection algorithm is resilient to common obfuscations used by hackers.
Published in the Proceedings of the 2005 IEEE Symposium on Security and Privacy (Oakland 2005), May 8-11, 2005, Oakland, CA, USA .
Presentation: Testing Malware Detectors
July 12, 2004
Abstract: display hide
In today's interconnected world, malware, such as worms and viruses, can cause havoc. A malware detector (commonly known as virus scanner) attempts to identify malware. In spite of the importance of malware detectors, there is a dearth of testing techniques for evaluating them. We present a technique based on program obfuscation for generating tests for malware detectors. Our technique is geared towards evaluating the resilience of malware detectors to various obfuscation transformations commonly used by hackers to disguise malware. We also demonstrate that a hacker can leverage a malware detector's weakness in handling obfuscation transformations and can extract the signature used by a detector for a specific malware. We evaluate three widely-used commercial virus scanners using our techniques and discover that the resilience of these scanners to various obfuscations is very poor.
Presented at the International Symposium on Software Testing and Analysis (ISSTA 2004), July 11-14, 2004, Boston, MA, USA .
Paper: Testing Malware Detectors
Mihai Christodorescu, Somesh Jha
July 12, 2004
Abstract: display hide
In today's interconnected world, malware, such as worms and viruses, can cause havoc. A malware detector (commonly known as virus scanner) attempts to identify malware. In spite of the importance of malware detectors, there is a dearth of testing techniques for evaluating them. We present a technique based on program obfuscation for generating tests for malware detectors. Our technique is geared towards evaluating the resilience of malware detectors to various obfuscation transformations commonly used by hackers to disguise malware. We also demonstrate that a hacker can leverage a malware detector's weakness in handling obfuscation transformations and can extract the signature used by a detector for a specific malware. We evaluate three widely-used commercial virus scanners using our techniques and discover that the resilience of these scanners to various obfuscations is very poor.
Published in the Proceedings of the International Symposium on Software Testing and Analysis (ISSTA 2004), July 11-14, 2004, Boston, MA, USA .
View paper: PDF:  20040712 - Testing Malware Detectors.pdf (11 pages, 340 kB)
( BibTeX entry )
, PS:  20040712 - Testing Malware Detectors.ps (11 pages, 653 kB)
( BibTeX entry )
, HTML:  index.html (108 kB)
( BibTeX entry )
, ACM Digital Library:  http://doi.acm.org/10.1145/1007512.1007518
Presentation: Static Analysis of Executables to Detect Malicious Patterns
August 7, 2003
Abstract: display hide
Malicious code detection is a crucial component of any defense mechanism. In this paper, we present a unique viewpoint on malicious code detection. We regard malicious code detection as an obfuscation-deobfuscation game between malicious code writers and researchers working on malicious code detection. Malicious code writers attempt to obfuscate the malicious code to subvert the malicious code detectors, such as anti-virus software. We tested the resilience of three commercial virus scanners against code obfuscation attacks. The results were surprising: the three commercial virus scanners could be subverted by very simple obfuscation transformations! We present an architecture for detecting malicious patterns in executables that is resilient to common obfuscation transformations. Experimental results demonstrate the efficacy of our prototype tool, SAFE (a static analyzer for executables).
Presented at the 12 USENIX Security Symposium (Security'03), August 4-8, 2003, Washington, DC, USA .
Paper: Static Analysis of Executables to Detect Malicious Patterns
Mihai Christodorescu, Somesh Jha
February 6, 2003
Abstract: display hide
Malicious code detection is a crucial component of any defense mechanism. In this paper, we present a unique viewpoint on malicious code detection. We regard malicious code detection as an obfuscation-deobfuscation game between malicious code writers and researchers working on malicious code detection. Malicious code writers attempt to obfuscate the malicious code to subvert the malicious code detectors, such as anti-virus software. We tested the resilience of three commercial virus scanners against code obfuscation attacks. The results were surprising: the three commercial virus scanners could be subverted by very simple obfuscation transformations! We present an architecture for detecting malicious patterns in executables that is resilient to common obfuscation transformations. Experimental results demonstrate the efficacy of our prototype tool, SAFE (a static analyzer for executables).
Published in the Proceedings of the 12th USENIX Security Symposium (Security'03), August 4-8, 2003, Washington, DC, USA .
Published as University of Wisconsin, Madison, Computer Sciences Department Technical Report # 1467 .
View paper: PDF:  20030206 - SAFE Static Analysis for Executables.pdf (21 pages, 334 kB) , PS:  safe_2003-02-06.ps (21 pages, 416 kB) , Compressed PS:  safe-tr_2003-02-10.ps.gz (21 pages, 104 kB)
(or copy on the UW CS tech report server: tr1467.ps.Z )
[UW CS technical report version]
( BibTeX entry )
, PDF:  20030807-StaticAnalysisOfExecutables... .pdf (18 pages, 303 kB)
[12th USENIX Security Symposium version]
( BibTeX entry )
, HTML:  index.html (259 kB)
[12th USENIX Security Symposium version]
( BibTeX entry )
Presentation: General Purpose Binary Rewriting
January 27, 2003
Abstract: display hide
A description of the architecture for a binary rewriting tool.
Presented at the MURI Meeting, January 2003, Williamsburg, VA, USA .
View paper: PDF:  20030127 - General Purpose Binary Rewriting.pdf (59 slides, 747 kB)
Presentation: Detection of Malicious Code Patterns in Executables via Model Checking
July 12, 2002
Abstract: display hide
A description of a malicious code detection tool that uses model checking ideas. We apply this tool to detecting viruses and explain our results.
Presented at the MURI Meeting, July 2002, Harpers Ferry, WV, USA .
Presentation: Virus Scanning as Model Checking
January 14, 2002
Abstract: display hide
A description of a virus scanner that uses model checking ideas.
Presented at the MURI Meeting, January 2002, Washington DC .
View paper: PDF:  20020114 - Virus Scanning as Model Checking.pdf (37 slides + 61 transition slides, 386 kB)
Presentation: Hardware Security Support in General Purpose Processors
December 10, 2001
Abstract: display hide
A performance analysis of the XOM architecture.
Written part of the coursework for UWisc CS 752 Advanced Computer Architecture, Fall 2001.
Presentation: Model Checking for Binaries
November 11, 2001
Abstract: display hide
A quick look into model checking of binaries, with an interesting application: virus scanning.
View paper: PDF:  20011108 - Model Checking for Binaries.pdf (19 slides, 88 kB)
Paper: Playing Inside the Black Box: Using Dynamic Instrumentation to Create Security Holes
February 9, 2001
Abstract: display hide
Programs running on insecure or malicious hosts have often been cited as ripe targets for security attacks. The enabling technology for these attacks is the ability to easily analyze and control the running program. Dynamic instrumentation provides the necessary technology for this analysis and control. As embodied in the DynInst API library, dynamic instrumentation allows easy construction of tools that can: (1) inspect a running process, obtaining structural information about the program; (2) control the execution of the program, (3) cause new libraries to be dynamically loaded into the process' address space; (4) splice new code sequences into the running program and remove them; and (5) replace individual call instructions or entire functions.
With this technology, we have provided two demonstrations of its use: exposing vulnerabilities in a distributed scheduling system (Condor), and bypassing access to a license server by a word processor (Framemaker). The first demonstration shows the danger of remote execution of a job on a system of unknown pedigree, and the second demonstration shows the vulnerabilities of software license protection schemes. While these types of vulnerabilities have long been speculated, we show how, with the right tool (the DynInst API), they can be easily accomplished. Along with this discussion of vulnerabilities, we also discuss strategies for compensating for them.
Published in the Proceedings of the Second Los Alamos Computer Science Institute Symposium, 2001 .
Published in Parallel Processing Letters, Vol. 11, Nos. 2 & 3 (2001), pp. 267-280 .
View paper: PDF:  20010209 - Playing Inside the Black Box... .pdf (11 pages, 84 kB)
Presentation: Bypassing License Checking Using Dyninst
March 24, 2000
Abstract: display hide
Presentation on how we used Dyninst to bypass license checks.
I presented the work I have done, with a couple of colleagues, on using Dyninst for dynamically modifying the behavior of a program while it is running. In our case, the modification we performed allowed us to bypass the checks for valid license.
Presented at the Paradyn Week, 2000 .
View paper: PDF:  20000327 - Bypassing License Checking Using Dyninst.pdf (19 slides, 88 kB)
Presentation: Active Storage Devices
March 6, 2000
Abstract: display hide
A quick survey of the research in active devices.
Written part of the coursework for UWisc CS 703 Advanced Topics in Programming Languages and Compilers, Spring 2000.
View paper: StarOffice SDD:  ActiveDevicesPresentation_2000March06.sdd (37 slides, 773 kB) , Web:  slideshow with notes (37 web pages)
Paper: Opening Pandora's Box: Using Binary Code Rewrite to Pypass License Checks
December 13, 1999
Abstract: display hide
A common method of enforcing software license terms is for a program to contact another program, called a license server, and ask for permission to run. This project attempts to bypass these license checks in a commercial product through runtime code modification, using the DynInst library.
The programs chosen as victims for this study are Adobe FrameMaker, the Purify family of programs, and MatLab. We successfully bypass the FrameMaker licensing checks, allowing full use of the product when the license server is unavailable. Limitations in DynInst prevent similar results with Purify or MatLab. A set of powerful tools has been developed and used in the process, and their generality should simplify similar license bypassing efforts on other software products.
Published as University of Wisconsin, Madison, Computer Sciences Department Technical Report # 1479 .
Written part of the coursework for UWisc CS 736 Advanced Operating Systems, Fall 1999.
View paper: PDF:  19991213 - Opening Pandora's Box... .pdf (26 pages, 254 kB) , Compressed PS:  tr1479.ps.Z (15 pages, 242 kB)
[UW CS technical report version]
Paper: SunOS 5.6 Kernel Performance Measurements
September 28, 1999
Abstract: display hide
I have performed time measurements on stock SunOS 5.6 / Ultra SPARC IIi to gauge the overhead of basic system calls (trivial calls, IPC, I/O, and memory-related). The benchmarking in itself was a challenge, because from user space there is tremendous indirection and associated overhead to each function call (library or system).
The 64-bit system call gethrtime() was found to be useful, with a high precision, very to the hardware clock precision of 3.3 ns. Several kernel calls were compared to find the kernel call overhead, and getpid() proved to be the fastest one. Signals- vs. pipes-based IPC comparisons clearly presented one-way unnamed pipe as a much better alternative. Further on, the latency of page faults for zero-filled pages revealed some high values, to be reckoned with when allocating large amount of memory. Finally, I have measured the basic read() system calls, along with its counterparts fread() and mmap(), and noticed that fread() performs much better that read() and that mmap() performance recommends it for small read buffer sizes.
The paper concludes by suggesting several ways to improve performance based on the measurements obtained, as well as by a short discussion on how to get relevant measurements. The topic is by no means open to further exploration.
Written part of the coursework for UWisc CS 736 Advanced Operating Systems, Fall 1999.
View paper: PDF:  os_measurements_uwcs736f1999.pdf (8 pages, 166k)
Paper: Illustration of GCC Compiler Optimizations for Ultra SPARC IIi
September 17, 1999
Abstract: display hide
The following code optimizations are illustrated: Redundant Expression Elimination (Common Subexpression Elimination), Partially Redundant Expression Elimination, Constant Propagation, Copy Propagation, Constant Folding, Dead Code Elimination, Loop Invariant Code Motion, Scalarization (Scalar Replacement), Local Register Allocation, Global Register Allocation, Interprocedural Register Allocation, Register Targeting, Interprocedural Code Motion, Call Inlining, Code Hoisting and Sinking, Loop Unrolling, Strength Reduction. Cache effects are briefly explained for data cache conflict misses and instruction cache loop unrolling.
Written part of the coursework for UWisc CS 701 Construction of Compilers, Fall 1999.
View paper: PDF:  compiler_optimizations_uwcs701f1999.pdf (23 pages, 42 kB)

Copyright 1998-2005 Mihai Christodorescu. All rights reserved.
Maintained by Mihai Christodorescu (http://mihai.christodorescu.org).
Created: Mon Dec 21 21:12:13 PST 1998
Last modified: Thu Nov 17 23:49:52 CST 2005