Splits the binary code parsing out into a separate component library.
[dyninst.git] / parseAPI / doc / parseapi.tex
1 \documentclass{tufte-handout}
2 \usepackage{amsmath}
3 \usepackage{amssymb}
4 \usepackage[protrusion,expansion=false,factor=1000,babel=false]{microtype}
5 \usepackage{enumitem}
6 \usepackage{booktabs}
7 \usepackage{algorithm}
8 \usepackage{algorithmic}
9 \usepackage{moreverb}
10 \usepackage{fancyvrb}
11 \fvset{fontsize=\normalsize}
12 \usepackage{tikz}
13 \usetikzlibrary{arrows,positioning,fit,decorations,decorations.pathmorphing,decorations.pathreplacing,calc,scopes,matrix}
14
15 \title{An API for Binary Code Parsing}
16 \author{Paradyn Parallel Performance Tools}
17
18 \begin{document}
19
20 \newcommand{\apient}[3]{%
21 #1 & #2 \\
22  & \emph{#3} \\[0.5em]%
23
24
25 \newenvironment{apilist}[1]{\begin{fullwidth}%
26 \begin{tabular}{p{0.25\linewidth}p{0.75\linewidth}}
27 {\bf #1} & \\%
28 }
29 {\end{tabular}\end{fullwidth}}
30
31
32 \maketitle
33
34
35 \section{Introduction}
36
37 \newthought{A binary code parser} converts the machine code representation of a
38 program, library, or code snippet to an abstraction of the instructions, basic
39 blocks, and functions that the binary code represents. The ParseAPI is a
40 multi-platform library for creating such abstractions from binary code sources.
41 The current incarnation uses SymtabAPI\cite{symtabsite} as the default binary
42 code source; all platforms and architectures handled by SymtabAPI are
43 supported. The ParseAPI is designed to be easily extensible to other binary
44 code sources. Support for parsing binary code in memory dumps or other formats
45 requires only implementation of a small interface as described in this
46 document.
47
48 This API provides the user with a control flow-oriented view of a binary code
49 source. Each code object such as a program binary or library is represented as
50 a top-level collection containing the functions, basic blocks, and edges that
51 represent the control flow graph. A simple query interface is provided for
52 retrieving lower level objects like functions and basic blocks through address
53 or other attribute lookup. These objects can be used to navigate the 
54 program structure as described below.
55
56 \subsection{Abstractions}
57
58 \begin{marginfigure}[2cm]
59 \centering
60 \begin{tikzpicture}[line width=1pt,x=\marginparwidth*.95/12,y=\marginparwidth*.95/12]
61
62 %\draw[help lines] (0,0) grid [step=1] (12,18) ;
63
64  %cfg nodes
65
66     \matrix (cfg1) [matrix of math nodes,
67              column sep={0.33cm},
68              row sep={0.6cm},
69              nodes={circle, draw, minimum size=0.5cm}]
70     {
71                & |(n1)| b_1 &    \\
72      |(n2)| b_2 &           & |(n3)| b_3 \\[1.1cm]
73      |(n4)| b_4 &           &    \\
74                & |(n5)| b_5 &    \\
75     };
76
77     \matrix [matrix of math nodes,
78              column sep={0.33cm},
79              row sep={0.6cm},
80              nodes={circle, draw, minimum size=0.5cm},
81              below right=-3.5 and -1 of cfg1]
82     {
83                & |(m1)| b_6 &    \\
84      |(m2)| b_7 &           & |(m3)| b_8 \\
85                & |(m4)| b_9 &    \\
86     };
87
88     \begin{scope}[>=stealth,->,looseness=0.5,auto,
89         every node/.style={font=\scriptsize\itshape}]
90         \draw (n1) to [bend right] (n2) ;
91         \draw (n1) to [bend left] (n3) ;
92         \draw (n2) to [bend left] (n4) ;
93         \draw (n4) to [bend left] (n2) ;
94         \draw (n4) to [bend right] (n5) ;
95         \draw (n3) to [bend left] (n5) ;
96         \draw (m1) to [bend right] (m2) ;
97         \draw (m1) to [bend left] (m3) ;
98         \draw (m2) to [bend right] (m4) ;
99         \draw (m3) to [bend left] (m4) ;
100         % call
101         \draw [dotted] (n3) to [bend left] node [midway] {call} (m1) ;
102     \end{scope}
103 \end{tikzpicture}
104 \caption{The control flow graph of two functions joined by an interprocedural \emph{call} edge.}
105 \end{marginfigure}
106
107 \newthought{The basic representation} of code in this API is the control flow
108 graph. The nodes of the CFG represent basic blocks: straight-line sequences of
109 instructions $I_i \ldots I_j$ where for each $i < k \le j$, $I_k$ postdominates
110 $I_{k-1}$. The typed edges between nodes in the graph represent execution
111 control flow, such as conditional and unconditional branches, fallthrough
112 edges, and calls. The graph therefore represents both \emph{inter-} and
113 \emph{intraprocedural} control flow: traversal of nodes and edges can cross the
114 bounaries of the higher level abstractions like \emph{functions}. Such
115 abstractions can nonetheless be obtained using this API.  A function represents
116 the set of all blocks reachable from a \emph{function entry point} through
117 intraprocedural control flow only. The entry points of functions are determined
118 by the parser library through various means, such as hints from debugging
119 symbols and recursive traversal along call edges.
120
121 \subsection{Interfaces}
122
123 The following classes define the publicly visible interfaces of the ParseAPI:
124
125 \begin{itemize}[label=$\circ$]
126 {\item {\sc codeobject}: represents the parsed form of a binary code object,
127 such as a program binary or library. Provides query access to CFG constructs
128 such as functions and basic blocks.}
129
130 {\item {\sc function}: represents a function and information about it, such as
131 its entry address, the list of blocks reachable through intraprocedural control
132 transfers, or whether the function is known to never return.}
133
134 {\item {\sc block}: represents a basic block, its start and end point, and control edges between the block and its successors and predecessors.}
135
136 {\item {\sc edge}: represents a control flow edge.}
137 \end{itemize}
138
139 \noindent
140 This API is meant to be extensible: with the exception of the CodeObject, all
141 of the default classes above can be extended to form the basis of some richer
142 abstraction over program control flow. Additionally, this API can be easily
143 applied to various code sources. The following interfaces are provided to
144 support extension to binary code sources besides those supported by the
145 SymtabAPI.
146
147 \begin{itemize}
148
149 {\item {\sc instructionsource}: represents an object from which pointers to machine instructions can be obtained. An InstructionSource implements a minimal contract as specified in the API details below.}
150
151 {\item {\sc codesource}: represents a binary code object. A CodeSource provides
152 access to the binary code through an InstructionSource, and optionally provides
153 a list of \emph{hints} that suggest starting locations for parsing, as well as
154 other binary characteristics like external linkage. For example, the provided
155 SymtabCodeSource specialization re-exports function symbols as hints for
156 parsing.}
157
158 {\item {\sc cfgfactory}: a factory for Function, Block, and Edge objects. A default allocator for these objects is provided. To use the parser with specialized extensions of the CFG objects, a custom CFGFactory that knows how to allocate such objects must implement the minimal contract of this interface.}
159
160 \end{itemize}
161
162 \section{A Simple Example}
163
164 The code example below illustrates how the ParseAPI can be used alongside of
165 the SymtabAPI to print out the control flow graph for a program binary.
166 \begin{listing}[1]{1}
167 using namespace Dyninst;
168 using namespace Dyninst::ParseAPI;
169
170 vector<Function *> funcs;
171
172 SymtabCodeSource * sts = new SymtabCodeSource("foobinary");
173 CodeObject * co = new CodeObject(sts);
174 \end{listing}
175 \noindent
176 Once the binary has been loaded (in this case using a SymtabAPI object as the
177 sbinary code source), it can be parsed and all of the functions can be
178 retrieved. The list of blocks reachable from each function can be retrieved
179 and output.\footnote{Alternatively, the intraprocedural control flow graph
180 for each function could be traversed starting with its first block by not
181 following \emph{call} edges.}
182
183 \begin{listingcont}
184 co->parse();
185
186 int cnt = co->allFuncs(funcs);
187 for(int i=0;i<fcnt;++i) {
188     const vector<Block *> & blocks = funcs[i]->blocks();
189     for(unsigned j=0;j<blocks.size();++j) {
190         vector<Edge *> & targets = blocks[j]->targets();
191         for(unsigned k=0;k<targets.size();++j) {
192             // print out block -> target
193         }
194     }
195 }
196 \end{listingcont}
197
198 \section{API Reference}
199
200 There are two major sections of the public API. The first is the CodeObject and
201 the CFG objects it provides access to; these represent the parsed program
202 binary. The second section is the interfaces necessary to extend the ParseAPI
203 to new binary code sources or to support specializations of the CFG objects.
204
205 \subsection{CFG Objects}
206
207 \begin{apilist}{CodeObject}
208 \apient{}{CodeObject(CodeSource * cs, CFGFactory * fact = NULL)}{Constructs a new CodeObject. The CodeSource argument is mandatory; if the CFGFactory argument is not provided, a default factory is used.}
209 \apient{void}{parse()}{Parses the binary code object using the default hint-based and recursive traversal algorithm.}
210 \apient{Function *}{findFuncByEntry(Address entry)}{Returns a pointer to the function starting at the given address or NULL.}
211 \apient{int}{findFuncs(Address addr, set<Function*> \& funcs)}{Finds all functions overlapping the given address, returning the number found.}
212 \apient{int}{allFuncs(set<Function*> \& funcs)}{Places all known functions in the provided set, returning the total number.}
213 \apient{int}{findBlocks(Address addr, set<Block*> \& blocks)}{Finds all blocks overlapping a given point. Blocks are allowed to overlap, as is possible on architectures with variable-length instruction sets.}
214 \apient{bool}{findCatchBlock(Address addr, Address \& catchStart)}{Finds the exception catch block covering the provided address, filling its starting point into catchStart if it exists.}
215 \apient{bool}{non\_returning(Address func\_entry)}{Queries CodeSource for known non-returning status of the function starting at func\_entry.}
216 \apient{bool}{non\_returning(string func\_name}{Queries CodeSource for known non-returning status of the named function.}
217 \end{apilist}
218
219 \begin{apilist}{Function}
220 \apient{}{Function(Address addr, CodeObject \& obj)}{Function constructor. The ParseAPI never calls this routine explicitly, instead using the CFGFactory mkfunc() method to allocate an object of the appropriate subclass.}
221 \apient{const char *}{name()}{Returns the name of the function.}
222 \apient{Address}{addr()}{Returns the function entry address.}
223 \apient{vector<Block *> \&}{blocks()}{Returns a reference to the vector of blocks reachable through intraprocedural control flow from this function entry point.}
224 \end{apilist}
225
226 \begin{apilist}{Block}
227 \apient{}{Block(Address start)}{Block constructor.}
228 \apient{Address}{start()}{Returns block start address.}
229 \apient{Address}{end()}{Returns block end address.}
230 \apient{Address}{last\_insn()}{Returns address of last instruction.}
231 \apient{Address}{size()}{Returns end() - start().}
232 \apient{vector<Edge*> \&}{sources()}{Returns vector of predecessor blocks in the control flow graph.}
233 \apient{vector<Edge*> \&}{targets()}{Returns vector of successor blocks in the control flow graph.}
234 \end{apilist}
235
236 \begin{apilist}{Edge}
237 \apient{}{Edge(Block * source, Block *target, EdgeTypeEnum type)}{Constructor.}
238 \apient{Block *}{src()}{Returns source component of this edge.}
239 \apient{Block *}{trg()}{Returns type component of this edge.}
240 \apient{EdgeTypeEnum}{type()}{Returns the edge type.}
241 \end{apilist}
242
243 \subsection{Extension Interface}
244
245 \begin{apilist}{CodeSource}
246 \apient{InstructionSource *}{isrc()}{Returns a pointer to an instruction source implementation. (implementation mandatory)}
247 \apient{vector<hint\_t> *}{hints()}{Returns a pointer to a vector of (location,name) pairs of function entry hints, or NULL if no such hints are provided by this code source. (implementation optional)}
248 \apient{bool}{non\_returning(Address func\_entry)}{Checks known non-returning status of the function starting at func\_entry. (implementation optional)}
249 \apient{bool}{non\_returning(string func\_name}{Checks known non-returning status of the named function. (implementation optional)}
250 \apient{map<Address,string> \&}{linkage()}{Returns external linkage map. (implementation optional)}
251 \end{apilist}
252
253 \begin{apilist}{InstructionSource}
254 \apient{bool}{isValidAddress(Address)}{}
255 \apient{void*}{getPtrToInstruction(Address)}{}
256 \apient{void*}{getPtrToData(Address)}{}
257 \apient{unsigned int}{getAddressWidth()}{}
258 \apient{bool}{isAligned(Address)}{}
259 \apient{bool}{isCode(Address)}{}
260 \apient{bool}{isData(Address)}{}
261 \apient{Address}{codeOffset()}{}
262 \apient{Address}{codeLength()}{}
263 \end{apilist}
264
265 \begin{apilist}{CFGFactory}
266 \apient{Function *}{mkfunc(Address addr, FuncSource src, CodeObject \& obj)}{}
267 \apient{Block *}{mkblock(Function * f, Address addr)}{}
268 \apient{Edge *}{mkedge(Block *src, Block *trg, EdgeTypeEnum type)}{}
269 \apient{void}{free\_func(Function *f)}{}
270 \apient{void}{free\_block(Block *b)}{}
271 \apient{void}{free\_edge(Edge *e)}{}
272 \apient{void}{free\_all()}{}
273 \end{apilist}
274
275
276 \bibliographystyle{plainnat}
277 \nobibliography{parseapi}
278
279 \end{document}