RomanGol avatar RomanGol committed 5dd1d16

Weekend Modification

rewrite design part

Comments (0)

Files changed (1)

APLAS2012/sec_design.tex

-\section{Design Principle of Lightweight Emulation}
+\section{Lightweight Emulation and Intermediate Language Transformation}
 \label{sec_lemu}
 Most of the traditional emulators are heavyweight and of full functionality.
 Now that emulator that supports full system characterization costs too much,
 The execution process highly depends on system or third-party APIs.
 The main factor that affects the emulation is how to implement these APIs imported in programs.
 Our solution for this problem is that the lightweight emulator doesn't handle the APIs,
-instead, it just handles plain instructions and considers the APIs as either black box state transitions or terminators,
-and the analyzed program is divided into many fragments.
-The lightweight emulator then deals with the code fragments.
-Moreover, function of APIs can be deployed as state transitions using other dynamic techniques such as debugging.
-The lightweight emulator connects these fragments with extra state transition information and fulfils long term emulation.
+instead, it just handles program's plain instructions and considers the APIs as external interfaces.
+The lightweight emulator leverages host platform to construct execution context, 
+and then deals with the program.
+Moreover, function of APIs can be achieved by host operating systems.
+The lightweight emulator connects emulated programs and external interfaces to fulfil completed emulation.
 
 % Our design inspiration of the lightweight emulator follows the philosophy of
 % simplescalar[], libemu[] and The  UNIX [http://www.linfo.org/unix\_philosophy.html].
-The implementation of lightweight emulator involves three aspects of work,
-\emph{emulator pruning, code fragment division, state reconstruction}.
+The implementation of lightweight emulator involves two aspects of work,
+\emph{emulator pruning, state reconstruction}.
 First, a pruning process on traditional full emulator architecture is executed to get a simple emulator.
-Then a code fragment division process is executed to search and test the code that is able to be lightweight emulated independently.
-Finally, the lightweight emulator needs reconstruct runtime context to fulfil the emulation.
+%Then a code fragment division process is executed to search and test the code that is able to be lightweight emulated independently.
+Then, the lightweight emulator needs reconstruct runtime context to fulfil the emulation.
 %Small is beautiful.  %Make each program do one thing well.  %Choose portability over efficiency.
+In addition, we extended the analysis work by introducing intermediate language as analyzing medium, 
+acquiring platform compatibility.
+
+\subsection{Emulator Pruning}
+As dynamic program analysis refers to a set of techniques that monitor the following behavior of an application while it is being executed.
+\begin{itemize}
+\item \emph{I/O and API invoking information}
+\item \emph{dynamic generated intermediate values}
+\item \emph{instruction execution sequence}
+\end{itemize}
+We observed that the acquiring of the first item can be well achieved by introducing system-level monitoring mechanism,
+while the acquiring of last two items is fulfilled only with the support of fine-granularity instruction level analysis.
+We propose the following emulator pruning principle in order to meet the requirements of instruction level analysis.
+A lightweight emulator is an emulator that supports core instructions of the emulated processor.
+It only reserves a virtual \emph{Execution Engine} and a virtual \emph{Machine State} to support instruction-level execution,
+and considers not of the conception of operating system, I/O or any other high-level runtime environments(See Fig~\ref{fig_pruning}).
+
+\begin{figure}[!t]
+\centering
+\includegraphics[width=2.7in]{pruning.png}
+\caption{Emulator Pruning}
+\label{fig_pruning}
+\end{figure}
+%The emulator is used as a filter that take program as input directly and outputs convenient data form.
 
 \subsubsection{Core Components}
+Basically, in order to emulate the processor the emulator has the following components:
 
-Basically, in order to emulate the processor and some operating system's
-functions, the emulator has the following components:
 \begin{description}
 \item [{CPU\ emulator}] When emulating a user-space process, every instruction
 in the process is emulated in the process emulator instead of running
 using the system API. Also, the emulator also maintains heaps and
 stacks of the process, which cannot be managed directly by the operating
 system.
-\item [{API\ hooking\ interface}] System calls(APIs) are handled directly
-by the operating system, through the API hooking interface provided
-by the emulator. Whenever a system API is called, the emulator intercepts
-the calling thread, reserves its context, converts its pointers from
-the emulated address space to the emulator's address space, then calls
-the actual API instead, and restore the thread's context in the end.
-In this way, the system APIs are directly executed by the operating
-system, which is the key of performance boost comparing to full-system
-emulation. There are a few exceptions. Some system APIs concerning
-the emulated OS features cannot by directly executed by the operating
-system, and have to be emulated. Such APIs include memory management,
-threading, module management, etc.
-\item [{Module\ loading}] Each process to emulate is in the form of a
-PE module, who has its dependent modules(dynamic-link libraries) which
-are also PE modules. The process loader in the emulator is responsible
-for loading the process and its dependent modules into the emulated
-memory space, handling their import and export functions, and handling
-relocations. Some of the system's core libraries, such as kernel32.dll,
-is not loaded into memory. API calls to these libraries is handled
-by the API hooking interface, as mentioned above.
-\item [{Callbacks\ and\ message\ handling}] Some of the Windows APIs
-contain callback functions, especially those concerning the message
-looping in Windows. In order to support system callback functions,
-we have to hook these callback functions within the emulator, where
-the parameters are extracted from the emulated memory, and the actual
-callback functions are called by the emulator. If the emulated has
-graphical user interface, its messages are passed to the emulator,
-and then handled by the emulated callback routines. Hence, the emulator
-cannot have a message loop, otherwise it cannot emulate programs with
-graphical user interface.
 \end{description}
+
 Program tracing becomes extremely easy using process emulation. Everything
 during execution is transparent to the analyst, including processor
 context, virtual memory, thread information, API calls, etc. Also,
 
 
 
-\subsection{Emulator Pruning}
-As dynamic program analysis refers to a set of techniques that monitor the following behavior of an application while it is being executed.
-\begin{itemize}
-\item \emph{I/O and API invoking information}
-\item \emph{dynamic generated intermediate values}
-\item \emph{instruction execution sequence}
-\end{itemize}
-We observed that the acquiring of the first item can be well achieved by introducing system-level monitoring mechanism,
-while the acquiring of last two items is fulfilled only with the support of fine-granularity instruction level analysis.
-We propose the following emulator pruning principle in order to meet the requirements of instruction level analysis.
-A lightweight emulator is an emulator that supports core instructions of the emulated processor.
-It only reserves a virtual \emph{Execution Engine} and a virtual \emph{Machine State} to support instruction-level execution,
-and considers not of the conception of operating system, I/O or any other high-level runtime environments(See Fig~\ref{fig_pruning}).
-
-\begin{figure}[!t]
-\centering
-\includegraphics[width=2.7in]{pruning.png}
-\caption{Emulator Pruning}
-\label{fig_pruning}
-\end{figure}
-%The emulator is used as a filter that take program as input directly and outputs convenient data form.
-
-\subsection{Code fragment division}
+%how many kinds of instructions are used? is there any privilege instructions or there are none?
+\subsection{Reconstruct Execution State}
 The main problem of the lightweight emulation is how to correctly execute programs without a full system emulated.
-In our scheme we don't emulate the entire program execution process.
+A lightweight emulator may not be able to correctly emulate code fragment simply because the execution context
+(e.g., value of registers, stacks) is incomplete.
+In our scheme we don't emulate the entire environment.
 Instead, our strategy of emulation and analysis is a divide-and-conquer strategy.
-That is to say, we search for code fragment that is logic-based and is easy to be emulated,
-and we apply lightweight emulation on these fragments.
+That is to say, our lightweight emulation runs under real operating system and 
 
-Our emulation process takes an \emph{ostrich approach}.
-That is to say, we ignore the implementation of potential complex platform related interfaces.
-This assumes that to emulate programs and analyze properties especially those related to logic or security,
-we need not deal with complex interfaces about high level UI interactions, API calls and third party libraries.
-And it is more cost-effective to allow the emulation to stop when encountering these functions rather than to attempt to fulfil them.
-Besides, we notice that in applications, small part of code can often be analyzed independently.
-Following facts support our observation.
-First, experienced reverse engineers know the approximate function of a code section at a glance.
-This is because compiler and linker tend to place codes with similar functions together.
-Code fragments that are used for OS-level or library-level interactions are commonly separated from those used for logical control or arithmetic operation.
-Second, most of the modern programs are written with high-level object-oriented programming languages such as C++ and Objective-C.
-The features of object-oriented programming such as encapsulation and modularity naturally bring independency of localized code fragments.
-For instance, a method of an object generally operates on data members of this object only and requires few external functions.
-Third, many modern programs follow the design principle of the Model-View-Controller (MVC) architecture.
-The Model-View-Controller architecture separates the modeling of the domain, the presentation, and the actions based on user input into three separate classes\cite{krasner1988description}.
-For applications, the Model-View-Controller architecture enforces the separation of logic code and GUI code,
-and thus lightweight analysis is reasonable.
 
-In our lightweight emulation we inherit Caballero et al.'s idea\cite{caballero2009binary} of finding code fragment.
-Furthermore, because the purpose of our work is to observe rather than to reuse the binary code,
-we loosen the restriction that the code fragment should contain clear interface.
-What we try to find is the smallest testable part of an application.
-A pre-process of code division is given by static analysis,
-which finds start point of basic blocks and functions etc.
-Then we suggest a test-and-stop methodology for code division.
-That is, for a program, we first set some start points
-(usually the start points of functions or basic blocks) and use a lightweight emulator to perform test from these points.
-The test simply checks whether or not the executed instruction is supported by the emulator.
-If the lightweight emulator throws an exception
-(e.g., encountering certain instruction or API call that is unavailable to execute), the end point of a code fragment is determined.
-After collecting code fragment a more fine analysis could be employed.
 
 \begin{figure}[!t]
 \centering
 \label{fig_lsim}
 \end{figure}
 
-%how many kinds of instructions are used? is there any privilege instructions or there are none?
-\subsection{Reconstruct Execution State}
-As mentioned above, one critical problem of the lightweight emulation,
-compared with full emulation, is the lack of execution context.
-A lightweight emulator may not be able to correctly emulate code fragment simply because the execution context
-(e.g., value of registers, stacks) is incomplete.
+
 The execution context may be self determined by code fragment, inherited from the invoker or from external libraries/system/devices.
 We define three general types of execution states during program execution,
 \begin{itemize}
         the I/O or other environmental reasons, it is unable to deduce the context except for a complete emulation.
 \end{itemize}
 
-As shown in fig~\ref{fig_pruning} the state of a lightweight emulator contains only necessary registers and values in memory.
-To reconstruct different states in a lightweight emulator, we adopt different strategies.
-For self contained state, we only need to initiate state with arbitrary or certain values.
-One typical situation is that an inner function is called by an outer function with certain arguments.
-The state is defined by these arguments.
-For reference state, it can be deduced for certain API calls are deterministic
-(e.g., the \emph{strlen} function) or the status of global variable is known.
-For the last situation, usually the state reconstruction is unavailable.
-If the emulator does need an external state,
-the state may be acquired by using either the original system monitoring or a full emulation,
-or even be defined by analyst herself.
-
-\begin{figure}[!t]
-\centering
-\includegraphics[width=3.3in]{states.png}
-\caption{Different situations of state}
-\label{fig_state}
-\end{figure}
-
-
-Fig~\ref{fig_state} shows typical samples of different states.
-In self contained state situation of Fig~\ref{fig_state}, the memory is initialized using static data, and thus it's easy to rebuild the context.
-In reference state situation of Fig~\ref{fig_state}, the function is self contained except for the value of memory address [4050AC].
-However, this value can be acquired by analyzing the original memory loading process.
-In the situation of external state in Fig~\ref{fig_state}, the state relies on API function \emph{GetCommandLineA} but the result is determined by runtime inputs.
-Thus in this situation analyst needs extra information to support reconstruction.
+\begin{itemize}
+\item [{API\ hooking\ interface}] System calls(APIs) are handled directly
+by the operating system, through the API hooking interface provided
+by the emulator. Whenever a system API is called, the emulator intercepts
+the calling thread, reserves its context, converts its pointers from
+the emulated address space to the emulator's address space, then calls
+the actual API instead, and restore the thread's context in the end.
+In this way, the system APIs are directly executed by the operating
+system, which is the key of performance boost comparing to full-system
+emulation. There are a few exceptions. Some system APIs concerning
+the emulated OS features cannot by directly executed by the operating
+system, and have to be emulated. Such APIs include memory management,
+threading, module management, etc.
+\item [{Module\ loading}] Each process to emulate is in the form of a
+PE module, who has its dependent modules(dynamic-link libraries) which
+are also PE modules. The process loader in the emulator is responsible
+for loading the process and its dependent modules into the emulated
+memory space, handling their import and export functions, and handling
+relocations. Some of the system's core libraries, such as kernel32.dll,
+is not loaded into memory. API calls to these libraries is handled
+by the API hooking interface, as mentioned above.
+\item [{Callbacks\ and\ message\ handling}] Some of the Windows APIs
+contain callback functions, especially those concerning the message
+looping in Windows. In order to support system callback functions,
+we have to hook these callback functions within the emulator, where
+the parameters are extracted from the emulated memory, and the actual
+callback functions are called by the emulator. If the emulated has
+graphical user interface, its messages are passed to the emulator,
+and then handled by the emulated callback routines. Hence, the emulator
+cannot have a message loop, otherwise it cannot emulate programs with
+graphical user interface.
+\end{itemize}
 
 
 
 
 
 \subsection{IL-based Program Analysis}
-The goal of our work is to automatically detect algorithms in binary
-software executables using dynamic methods. To address the issues
-of dynamic data pattern analysis, we further extended this method
-by introducing intermediate language as analyzing medium, increasing
-its efficiency and accuracy, and acquiring platform compatibility
-at the same time.
-
-In this section, we'll first introduce the design principles of the
-intermediate language, and then talk about detailed description of
-each step of analysis based on the intermediate language.
-
-
-
-\subsubsection{Design Principles of Intermediate Language}
-
 Runtime data in dynamic program analysis is generated by program tracing,
 and in our case, through program emulation. As we know, dynamic program
 tracing usually produces low-level, fine-grained program data. For
Tip: Filter by directory path e.g. /media app.js to search for public/media/app.js.
Tip: Use camelCasing e.g. ProjME to search for ProjectModifiedEvent.java.
Tip: Filter by extension type e.g. /repo .js to search for all .js files in the /repo directory.
Tip: Separate your search with spaces e.g. /ssh pom.xml to search for src/ssh/pom.xml.
Tip: Use ↑ and ↓ arrow keys to navigate and return to view the file.
Tip: You can also navigate files with Ctrl+j (next) and Ctrl+k (previous) and view the file with Ctrl+o.
Tip: You can also navigate files with Alt+j (next) and Alt+k (previous) and view the file with Alt+o.