Workarounds for old buggy versions of PGF (for ParseAPI manual front page)
[dyninst.git] / parseAPI / doc / parseapi.tex
1 \documentclass{article}
2
3 \usepackage{booktabs}
4 \usepackage{color}
5 \usepackage{pgf}
6 \usepackage{tikz}
7 \usetikzlibrary{arrows,positioning,fit,shapes,decorations,decorations.pathmorphing,decorations.pathreplacing,calc,patterns,scopes,matrix}
8 \pgfrealjobname{parseapi}
9
10 \usepackage{helvet}
11 \usepackage{enumitem}
12 \usepackage[letterpaper]{geometry}
13 \usepackage{listings}
14 \usepackage{verbatim}
15 \usepackage[T1]{fontenc}
16
17 \setlength{\parindent}{0.0in}
18 \setlength{\parskip}{0.1in}
19
20 \newenvironment{apient}{\small\verbatim}{\endverbatim}
21
22 \newcommand{\apidesc}[1]{%
23 {\addtolength{\leftskip}{4em}%
24 #1\par\medskip}
25 }
26
27 \begin{document}
28 \thispagestyle{empty}
29
30 \begin{titlepage}
31 \beginpgfgraphicnamed{titlepage}
32 \begin{tikzpicture}[remember picture, overlay]
33     \path
34         (current page.north west) coordinate (origin)
35         (current page.north) coordinate (topcenter);
36
37     % Header
38     \node [font=\sffamily] (pppt) at ($(topcenter) - (0,1.0in)$) 
39         {\fontsize{24}{36}\selectfont Paradyn Parallel Performance Tools};
40
41     % Document Title
42 % older versions of pgf have a bug for matrices in overlay mode;
43 % have to specify positions manually
44 %    \matrix (Title) [%
45 %        matrix of nodes,%
46 %        nodes={font=\sffamily,right},%
47 %        matrix anchor=west,%
48 %        row sep=12pt
49 %        ] at ($(origin)+(0.75in,-3.0in)$)
50 %    {
51 %        \fontsize{48}{56}\selectfont ParseAPI \\
52 %        \fontsize{44}{56}\selectfont Programmer's Guide \\
53 %    };
54
55     \node [anchor=west,font=\sffamily] (title1) at ($(origin)+(0.75in,-3.0in)$)
56         {\fontsize{48}{56}\selectfont ParseAPI};
57     \node [anchor=west,font=\sffamily] (title2) at ($(title1.west)+(0in,-56pt)$)
58         {\fontsize{48}{56}\selectfont Programmer's Guide};
59
60     % Release information
61 %    \matrix (Releaseinfo) [%
62 %        matrix of nodes,%
63 %        nodes={font=\sffamily,right},%
64 %        matrix anchor=west,%
65 %        row sep=8pt
66 %        ] at ($(origin)+(0.75in,-5.0in)$)
67 %    {
68 %        %\fontsize{24}{32}\selectfont Release 0.1 \\
69 %        \fontsize{24}{32}\selectfont Beta Release \\
70 %        \fontsize{24}{32}\selectfont Oct 2010 \\
71 %    };
72
73     \node [anchor=west,font=\sffamily] (rel1) at ($(origin)+(0.75in,-5.0in)$)
74         {\fontsize{24}{32}\selectfont Beta Release};
75     \node [anchor=west,font=\sffamily] (rel2) at ($(rel1.west)+(0in,-32pt)$)
76         {\fontsize{24}{32}\selectfont Oct 2010};
77
78     % Contact information
79 %    \matrix (UWaddress) [%
80 %        matrix of nodes,%
81 %        nodes={font=\sffamily\large,right},%
82 %        matrix anchor=north west
83 %        ] at ($(origin)+(0.75in,-7in)$)
84 %    {
85 %        Computer Science Department \\
86 %        University of Wisconsin--Madison \\
87 %        Madison, WI 53711 \\
88 %    };
89
90     \node [anchor=west,font=\sffamily\large] (uw1) at ($(origin)+(0.75in,-7.0in)$)
91         {Computer Science Department};
92     \node [anchor=west,font=\sffamily\large] (uw2) at ($(uw1.west)+(0in,-20pt)$)
93         {University of Wisconsin--Madison};
94     \node [anchor=west,font=\sffamily\large] (uw3) at ($(uw2.west)+(0in,-20pt)$)
95         {Madison, WI 53711};
96
97
98 %    \matrix (UMDaddress) [%
99 %        matrix of nodes,%
100 %        nodes={font=\sffamily\large,right},%
101 %        matrix anchor=north west,
102 %        below=1em of UWaddress.south west
103 %        ]
104 %    {
105 %        Computer Science Department \\
106 %        University of Maryland \\
107 %        College Park, MD 20742 \\
108 %    };
109
110     \node [anchor=west,font=\sffamily\large] (umd1) at ($(uw3.south west)+(0in,-2.5em)$)
111         {Computer Science Department};
112     \node [anchor=west,font=\sffamily\large] (umd2) at ($(umd1.west)+(0in,-20pt)$)
113         {University of Maryland};
114     \node [anchor=west,font=\sffamily\large] (umd3) at ($(umd2.west)+(0in,-20pt)$)
115         {College Park, MD 20742};
116
117 %    \matrix (Emails) [%
118 %        matrix of nodes,%
119 %        nodes={font=\sffamily,right},%
120 %        matrix anchor=north west,%
121 %        below=1em of UMDaddress.south west,%
122 %        anchor=base
123 %        ]
124 %    {
125 %        Email & \texttt{bugs@dyninst.org} \\
126 %        Web & \texttt{www.dyninst.org} \\
127 %    };
128
129     \node [anchor=west,font=\sffamily] (email1) at ($(umd3.south west)+(-0.5em,-2.5em)$)
130         %{Email \texttt{bugs@dyninst.org}};
131         {\begin{tabular}{ll}%
132          Email & \texttt{bugs@dyninst.org} \\
133          Web & \texttt{www.dyinst.org} \\
134         \end{tabular}};
135         
136
137     % Logo
138     \path 
139         node (logo) at ($(origin)+(4.0in,-7.0in)$) [%
140             anchor=north west]
141         {%
142             \includegraphics[width=3.25in]{paradyn_logo}
143         }; 
144
145
146 \end{tikzpicture}
147 \endpgfgraphicnamed
148 \end{titlepage}
149
150 \tableofcontents
151 \clearpage
152
153 \section{Introduction}
154 \label{sec:intro}
155
156 A binary code parser converts the machine code representation of a
157 program, library, or code snippet to an abstraction of the instructions, basic
158 blocks, and functions that the binary code represents. The ParseAPI is a
159 multi-platform library for creating such abstractions from binary code sources.
160 The current incarnation uses SymtabAPI as the default binary code source; all
161 platforms and architectures handled by SymtabAPI are supported. The ParseAPI is
162 designed to be easily extensible to other binary code sources. Support for
163 parsing binary code in memory dumps or other formats requires only
164 implementation of a small interface as described in this document.
165
166 This API provides the user with a control flow-oriented view of a binary code
167 source. Each code object such as a program binary or library is represented as
168 a top-level collection containing the functions, basic blocks, and edges that
169 represent the control flow graph. A simple query interface is provided for
170 retrieving lower level objects like functions and basic blocks through address
171 or other attribute lookup. These objects can be used to navigate the
172 program structure as described below.
173
174 \emph{The ParseAPI is currently released as a public beta. The interfaces described in this manual are subject to change in future versions. Feedback and comments are welcome; please email bugs@dyninst.org.}
175
176 \section{Abstractions}
177 \label{sec:abstractions}
178
179 The basic representation of code in this API is the control flow
180 graph (CFG). Binary code objects are represented as regions of contiguous bytes that, when parsed, form the nodes and edges of this graph. The following abstractions make up this CFG-oriented representation of binary code:
181
182 % CFG representation abastractions
183 %
184 % Function, Block, and Edge
185 \begin{itemize}[leftmargin=0pt,label=$\circ$]
186
187
188 {\item {\scshape block}: Nodes in the CFG represent \emph{basic blocks}:
189 straight line sequences of instructions $I_i \ldots I_j$ where for each $i < k
190 \le j$, $I_k$ postdominates $I_{k-1}$. Importantly, on some instruction set architectures basic blocks can \emph{overlap} on the same address range---variable length instruction sets allow for multiple interpretations of the bytes making up the basic block.
191 }
192
193 {\item {\scshape edge}: Typed edges beween the nodes in the CFG represent
194 execution control flow, such as conditional and unconditional branches,
195 fallthrough edges, and calls and returns. The graph therefore represents both
196 \emph{inter-} and \emph{intraprocedural} control flow: travseral of nodes and
197 edges can cross the boundaries of the higher level abstractions like
198 \emph{functions}.
199 }
200
201 {\item {\scshape function}: The \emph{function} is the primary semantic grouping of code in the binary, mirroring the familiar abstraction of procedural languages like C. Functions represent the set of all basic blocks reachable from a \emph{function entry point} through intraprocedural control flow only (that is, no calls or returns). Function entry points are determined in a variety of ways, such as hints from debugging symbols and recursive traversal along call edges.
202 }
203
204 \end{itemize}
205
206 % binary code representation abstractions
207 %
208 % code object, code source, and instruction source
209 \begin{itemize}[leftmargin=0pt,label=$\circ$]
210
211 {\item {\scshape code object}: A collection of distinct code regions are represented as a single code object, such as an executable or library. Code objects can normally be thought of as a single, discontiguous unique address space. However, the ParseAPI supports code objects in which the different regions have overlapping address spaces, such as UNIX archive files containing unlinked code.
212 }% end code object
213
214 {\item {\scshape instruction source}: An instruction source describes a backing store containing binary code. A binary file, a library, a memory dump or a process's executing memory image can all be described as an instruction source, allowing parsing of a variety of binary code objects.
215 }% end instruction source
216
217 {\item {\scshape code source}: The code source implements the instruction source interface, exporting methods that can access the underlying bytes of the binary code for parsing. It also exports a number of additional helper methods that do things such as returning the location of structured exception handling routines and function symbols. Code sources are tailored to particular binary types; the ParseAPI provides a SymtabAPI-based code source that understands ELF, COFF and PE file formats.
218 }% end code source
219
220 \end{itemize}
221
222 \section{A simple example}
223 \label{sec:example}
224
225 The following complete example uses the ParseAPI to parse a binary and dump its control flow graph in the Graphviz file format.
226
227 \lstset{language=[GNU]C++,basicstyle=\fontfamily{fvm}\selectfont\small}
228 \lstset{numbers=left, numberstyle=\tiny, stepnumber=5, numbersep=5pt}
229 \lstinputlisting{example.cc}
230
231 \section{The Parsing API}
232 \label{sec:api}
233
234 \subsection{Class CodeObject}
235
236 The CodeObject class describes an individual binary code object, such as an
237 executable or library. It is the top-level container for parsing the object as
238 well as accessing that parse data. The following API routines and data types
239 are provided to support parsing and retrieving parsing products.
240
241 \begin{apient}
242 typedef ContainerWrapper<vector<Function*>,Function*,Function*> funclist
243 \end{apient}
244 \apidesc{Container for access to functions. Refer to Section \ref{sec:containers} for details. Library users \emph{must not} rely on the underlying container type of ContainerWrapper lists, as it is subject to change.}
245
246 \begin{apient}
247 CodeObject(CodeSource * cs,
248     CFGFactory * fact = NULL,
249     ParseCallback * cb = NULL,
250     bool defensiveMode = false)
251 \end{apient}
252 \apidesc{Constructs a new CodeObject from the provided CodeSource and
253 optional object factory and callback handlers. Any parsing hints provided
254 by the CodeSource are processed, but the binary is not parsed when this
255 constructor returns.
256
257 \medskip\noindent The \texttt{defensiveMode}
258 parameter optionally trades off coverage for safety; this mode is not
259 recommended for most applications as it makes very conservative assumptions
260 about control flow transfer instructions (see Section \ref{sec:defmode}.}
261
262 \begin{apient}
263 void parse()
264 \end{apient}
265 \apidesc{Recursively parses the binary represented by this CodeObject from all
266 known function entry points (i.e., the hints provided by the CodeSource).}
267
268 \begin{apient}
269 void parse(Address target, bool recursive)
270 \end{apient}
271 \apidesc{Parses the binary starting with the instruction at the provided target address. If \texttt{recursive} is {\scshape true}, recursive traversal parsing is used as in the default \texttt{parse()} method; otherwise only instructions reachable through intraprocedural control flow are visited.}
272
273 \begin{apient}
274 void parseGaps(CodeRegion *cr)
275 \end{apient}
276 \apidesc{Speculatively parse the indicated region of the binary using pattern matching to find likely function entry points. Only enabled on the x86 32-bit platform.}
277
278 \begin{apient}
279 Function * findFuncByEntry(CodeRegion * cr, Address entry)
280 \end{apient}
281 \apidesc{Find the function starting at address \texttt{entry} in the indicated CodeRegion. Returns {\scshape null} if no such function exists.}
282
283 \begin{apient}
284 int findFuncs(CodeRegion * cr, Address addr, std::set<Function*> & funcs)
285 \end{apient}
286 \apidesc{Finds all functions spanning \texttt{addr} in the code region, adding each to \texttt{funcs}. The number of results of this stabbing query are returned.}
287
288 \begin{apient}
289 funclist & funcs()
290 \end{apient}
291 \apidesc{Returns a reference to a container of all functions in the binary. Refer to Section \ref{sec:containers} for container access details.}
292
293 \begin{apient}
294 Block * findBlockByEntry(CodeRegion * cr, Address entry)
295 \end{apient}
296 \apidesc{Find the basic block starting at address \texttt{entry}. Returns {\scshape null} if no such block exists.}
297
298 \begin{apient}
299 int findBlocks(CodeRegion * cr, Address addr, std::set<Block*> & blocks)
300 \end{apient}
301 \apidesc{Finds all blocks spanning \texttt{addr} in the code region, adding each to \texttt{blocks}. Multiple blocks can be returned only on platforms with variable-length instruction sets (such as IA32) for which overlapping instructions are possible; at most one block will be returned on all other platforms.}
302
303 \begin{apient}
304 void finalize()
305 \end{apient}
306 \apidesc{Force complete parsing of the CodeObject; parsing operations are otherwise completed only as needed to answer queries.}
307
308 \begin{apient}
309 CodeSource * cs()
310 \end{apient}
311 \apidesc{Return a reference to the underlying CodeSource.}
312
313 \begin{apient}
314 CFGFactory * fact()
315 \end{apient}
316 \apidesc{Return a reference to the CFG object factory.}
317
318 \subsection{Class CodeSource}
319 \label{sec:codesource}
320
321 The CodeSource interface is used by the ParseAPI to retrieve binary code from an executable, library, or other binary code object; it also can provide hints of function entry points (such as those derived from debugging symbols) to seed the parser. The ParseAPI provides a default implementation based on the SymtabAPI that supports many common binary formats. For details on implementing a custom CodeSource, see Appendix \ref{sec:extend}.
322
323 \begin{apient}
324 virtual bool nonReturning(Address func_entry)
325 virtual bool nonReturning(std::string func_name)
326 \end{apient}
327 \apidesc{Looks up whether a function returns (by name or location). This information may be statically known for some code sources, and can lead to better parsing accuracy.}
328
329 \begin{apient}
330 virtual Address baseAddress()
331 virtual Address loadAddress()
332 \end{apient}
333 \apidesc{If the binary file type supplies non-zero base or load addresses (e.g. Windows PE), implementations should override these functions.}
334
335 \begin{apient}
336 std::map< Address, std::string > & linkage()
337 \end{apient}
338 \apidesc{Returns a reference to the external linkage map, which may or may not be filled in for a particular CodeSource implementation.}
339
340 \begin{apient}
341 std::vector<CodeRegion *> const& regions()
342 \end{apient}
343 \apidesc{Returns a read-only vector of code regions within the binary represented by this code source.}
344
345 \begin{apient}
346 int findRegions(Address addr, set<CodeRegion *> & ret)
347 \end{apient}
348 \apidesc{Finds all CodeRegion objects that overlap the provided address. Some code sources (e.g. archive files) may have several regions with overlapping address ranges; others (e.g. ELF binaries) do not.}
349
350 \begin{apient}
351 bool regionsOverlap() 
352 \end{apient}
353 \apidesc{Indicates whether the CodeSource contains overlapping regions.}
354
355 \subsection{Class CodeRegion}
356
357 The CodeRegion interface is an accounting structure used to divide CodeSources into distinct regions. This interface is mostly of interest to CodeSource implementors.
358
359 \begin{apient}
360 void names(Address addr, vector<std::string> & names)
361 \end{apient}
362 \apidesc{Fills the provided vector with any names associated with the function at a given address in the region, e.g. symbol names in an ELF or PE binary.}
363
364 \begin{apient}
365 virtual bool findCatchBlock(Address addr, Address & catchStart)
366 \end{apient}
367 \apidesc{Finds the exception handler associated with an address, if one exists. This routine is only implemented for binary code sources that support structured exception handling, such as the SymtabAPI-based SymtabCodeSource provided as part of the ParseAPI.}
368
369 \begin{apient}
370 Address low()
371 \end{apient}
372 \apidesc{The lower bound of the interval of address space covered by this region.}
373
374 \begin{apient}
375 Address high()
376 \end{apient}
377 \apidesc{The upper bound of the interval of address space covered by this region.}
378
379 \begin{apient}
380 bool contains(Address addr)
381 \end{apient}
382 \apidesc{Returns {\scshape true} if $\texttt{addr} \in [\texttt{low()},\texttt{high()})$, {\scshape false} otherwise.}
383
384 \subsection{Class Function}
385
386 The Function class represents the protion of the program CFG that is reachable through intraprocedural control flow transfers from the function's entry block. Functions in the ParseAPI have only a single entry point; multiple-entry functions such as those found in Fortran programs are represented as several functions that ``share'' a subset of the CFG. 
387
388 \begin{center}
389 \begin{tabular}{ll}
390 \toprule
391 FuncSource & Meaning \\
392 \midrule
393 RT & recursive traversal (default) \\
394 HINT & specified in CodeSource hints \\
395 GAP & speculative parsing heuristics \\
396 GAPRT & recursive traversal from speculative parse \\
397 ONDEMAND & dynamically discovered at runtime \\
398 \bottomrule
399 \end{tabular}
400 \end{center}
401
402 \apidesc{Return type of function \typett{src()} see description below.}
403
404 \begin{center}
405 \begin{tabular}{ll}
406 \toprule
407 FuncReturnStatus & Meaning \\
408 \midrule
409 UNSET & unparsed function (default) \\
410 NORETURN & will not return \\
411 UNKNOWN & cannot be determined statically \\
412 RETURN & may return \\
413 \bottomrule
414 \end{tabular}
415 \end{center}
416
417 \apidesc{Return type of function \texttt{retstatus()}, see description below.}
418
419 \begin{apient}
420 typedef ContainerWrapper<vector<Block*>,Block*,Block*> blocklist
421 typedef ContainerWrapper<vector<Edge*>,Edge*,Edge*> edgelist
422 \end{apient}
423 \apidesc{Containers for block and edge access. Refer to Section \ref{sec:containers} for details on \texttt{ContainerWrapper}. Library users \emph{must not} rely on the underlying container type of ContainerWrapper lists, as it is subject to change.}
424
425 \begin{apient}
426 const string & name()
427 \end{apient}
428 \apidesc{Returns the name of this function.}
429
430 \begin{apient}
431 CodeRegion * region()
432 \end{apient}
433 \apidesc{Returns the CodeRegion that contains this function's entry point (functions can span multiple regions).}
434
435 \begin{apient}
436 InstructionSource * isrc()
437 \end{apient}
438 \apidesc{Returns the InstructionSource for this function.}
439
440 \begin{apient}
441 CodeObject * obj()
442 \end{apient}
443 \apidesc{Returns the CodeObject containing this function.}
444
445 \begin{apient}
446 FuncSource src()
447 \end{apient}
448 \apidesc{Returns the type of hint that identified this function's entry point.}
449
450 \begin{apient}
451 FuncReturnStatus retstatus()
452 \end{apient}
453 \apidesc{Returns the best-effort determination of whether this function may return or not. Return status cannot always be statically determined, and at most can guarantee that a function \emph{may} return, not that it \emph{will} return.}
454
455 \begin{apient}
456 Block * entry()
457 \end{apient}
458 \apidesc{Returns the basic block at this function's entry point.}
459
460 \begin{apient}
461 bool parsed()
462 \end{apient}
463 \apidesc{Indicates whether this function has been parsed.}
464
465 \begin{apient}
466 blocklist & blocks()
467 \end{apient}
468 \apidesc{Returns a list of the basic blocks comprised by this function. The blocks are guaranteed to be sorted by starting address.}
469
470 \begin{apient}
471 bool contains(Block *b)
472 \end{apient}
473 \apidesc{Returns {\scshape true} if the block is contained in this function.}
474
475 \begin{apient}
476 edgelist & callEdges()
477 \end{apient}
478 \apidesc{Returns a list of all outgoing call edges from this function.}
479
480 \begin{apient}
481 blocklist & returnBlocks()
482 \end{apient}
483 \apidesc{Returns a list of all blocks ending in a \texttt{return} instruction.}
484
485 \begin{apient}
486 std::vector<FuncExtent *> const& extents()
487 \end{apient}
488 \apidesc{Returns a list of contiguous extents of binary code within the function.}
489
490 [The following methods provide additional details about functions to support instrumentation applications and are probably of no interest to most users.]
491
492 \begin{apient}
493 bool hasNoStackFrame()
494 \end{apient}
495 \apidesc{Indicates whether the function sets up a stack frame.}
496
497 \begin{apient}
498 bool savesFramePointer()
499 \end{apient}
500 \apidesc{Indicates whether the function saves a stack frame pointer.}
501
502 \begin{apient}
503 bool cleansOwnStack()
504 \end{apient}
505 \apidesc{Indicates whether the function tears down its own stack on return.}
506
507 \subsection{Class FuncExtent}
508
509 Function Extents are used internally for accounting and lookup purposes. They may be useful for users who wish to precisely identify the ranges of the address space spanned by functions (functions are often discontiguous, particularly on architectures with variable length instruction sets).
510
511 \begin{apient}
512 Address start()
513 \end{apient}
514 \apidesc{The start of this contiguous code extent.}
515
516 \begin{apient}
517 Address end()
518 \end{apient}
519 \apidesc{The end of this contiguous code extent (exclusive).}
520
521 \subsection{Class Block}
522
523 A Block represents a basic block as defined in Section \ref{abstractions}, and is the lowest level representation of code in the CFG.
524
525 \begin{apient}
526 typedef ContainerWrapper<vector<Edge*>,Edge*,Edge*> edgelist
527 \end{apient}
528 \apidesc{Container for edge access. Refer to Section \ref{sec:containers} for details. Library users \emph{must not} rely on the underlying container type of ContainerWrapper lists, as it is subject to change.}
529
530
531 \begin{apient}
532 Address start()
533 \end{apient}
534 \apidesc{Returns the lower bound of this block.}
535
536 \begin{apient}
537 Address end()
538 \end{apient}
539 \apidesc{Returns the upper bound of this block.}
540
541 \begin{apient}
542 Address lastInsnAddr()
543 \end{apient}
544 \apidesc{Returns the address of the last instruction in this block.}
545
546 \begin{apient}
547 Address size()
548 \end{apient}
549 \apidesc{Returns $\texttt{end()} - \texttt{start()}$.}
550
551 \begin{apient}
552 bool parsed()
553 \end{apient}
554 \apidesc{Indicates whether this block has been parsed.}
555
556 \begin{apient}
557 CodeObject * obj()
558 \end{apient}
559 \apidesc{Returns the CodeObject containing this block.}
560
561 \begin{apient}
562 CodeRegion * region()
563 \end{apient}
564 \apidesc{Returns the CodeRegion containing this block.}
565
566 \begin{apient}
567 edgelist & sources()
568 \end{apient}
569 \apidesc{Return a list of all incomming edges to the block.}
570
571 \begin{apient}
572 edgelist & targets()
573 \end{apient}
574 \apidesc{Return a list of all outgoing edges from the block.}
575
576 \begin{apient}
577 bool consistent(Address addr, Address & prev_insn)
578 \end{apient}
579 \apidesc{Check whether address \texttt{addr} is \emph{consistent} with this basic block. An address is consistent if it is the boundary between two instructions in the block. As long as \texttt{addr} is within the range of the block, \texttt{prev\_insn} will contain the address of the previous instruction boundary before \texttt{addr}, regardless of whether \texttt{addr} is consistent or not.}
580
581 \begin{apient}
582 int containingFuncs()
583 \end{apient}
584 \apidesc{Returns the number of functions that contain this block.}
585
586 \begin{apient}
587 void getFuncs(std::vector<Function *> & funcs)
588 \end{apient}
589 \apidesc{Fills in the provided vector with all functions that share this basic block.}
590
591 \subsection{Class Edge}
592
593 Typed Edges join two blocks in the CFG, indicating the type of control flow
594 transfer instruction that joins the blocks to each other. Edges may not correspond
595 to a control flow transfer instruction at all, as in the case of the {\scshape
596 fallthrough} edge that indicates where straight-line control flow is split by
597 incoming transfers from another location, such as a branch. While not all
598 blocks end in a control transfer instruction, all control transfer instructions
599 end basic blocks and have outgoing edges; in the case of unresolvable control
600 flow, the edge will target a special ``sink'' block (see \texttt{sinkEdge()},
601 below.
602
603 \begin{center}
604 \begin{tabular}{ll}
605 \toprule
606 EdgeTypeEnum & Meaning \\
607 \midrule
608 CALL & call edge \\
609 COND\_TAKEN & conditional branch--taken \\
610 COND\_NOT\_TAKEN & conditional branch--not taken \\
611 INDIRECT & branch indirect \\
612 DIRECT & branch direct \\
613 FALLTHROUGH & direct fallthrough (no branch) \\
614 CATCH & exception handler \\
615 CALL\_FT & post-call fallthrough \\
616 RET & return \\
617 \bottomrule
618 \end{tabular}
619 \end{center}
620
621 \begin{apient}
622 Block * src()
623 \end{apient}
624 \apidesc{Returns the source block of this edge.}
625
626 \begin{apient}
627 Block * trg()
628 \end{apient}
629 \apidesc{Returns the target block of this edge.}
630
631 \begin{apient}
632 EdgeTypeEnum type()
633 \end{apient}
634 \apidesc{Returns the edge type.}
635
636 \begin{apient}
637 bool sinkEdge()
638 \end{apient}
639 \apidesc{Indicates whether this edge targets the special \emph{sink} block.}
640
641 \begin{apient}
642 bool interproc()
643 \end{apient}
644 \apidesc{Returns {\scshape true} if the edge should be interpreted as interprocedural (e.g. calls, returns, direct branches under certain circumstances).}
645
646 \subsection{Class EdgePredicate}
647 \label{sec:pred}
648
649 Edge predicates control iteration over edges. For example, the provided
650 \texttt{Intraproc} edge predicate can be passed to an edge iterator
651 constructor, ensuring that only intraprocedural edges are visited during
652 iteration. Two other implementations of EdgePredicate are provided: 
653 \texttt{SingleContext} only visits edges that stay in a single
654 function context, and \texttt{NoSinkPredicate} does not visit edges to 
655 the \emph{sink} block.  The following code traverses 
656 all of the basic blocks within a
657 function:
658
659 \lstset{language=[GNU]C++,basicstyle=\fontfamily{fvm}\selectfont\small}
660 \lstset{numbers=left, numberstyle=\tiny, stepnumber=5, numbersep=5pt}
661 \begin{lstlisting}
662     vector<Block*> work;
663     std::map<Block*,bool> seen; // avoid loops
664     Intraproc epred; // ignore calls, returns
665    
666     work.push_back(func->entry()); // assuming `func' is a Function*
667     seen[func->entry()] = true;
668     while(!work.empty()) {
669         Block * b = work.back();
670         work.pop_back();
671
672         // do some stuff with b...
673    
674         Block::edgelist & targets = block->targets();
675         Block::edgelist::iterator eit = targets.begin(&epred);
676         for( ; eit != targets.end(); ++eit) {
677             Edge * e = (*eit);
678             if(seen.find(e->trg()) == seen.end())
679                 work.push_back(e->trg());
680         }
681     } 
682 \end{lstlisting}
683
684 New edge predicates can be created by implementing the following simple interface:
685
686 \begin{apient}
687 EdgePredicate()
688 EdgePredicate(EdgePredicate * next)
689 \end{apient}
690 \apidesc{Constructs a predicate, either with or without a previously existing predicate to chain it to. Chained predicates return the logical AND over all predicates in the chain.}
691
692 \begin{apient}
693 virtual bool pred_impl(Edge *)
694 \end{apient}
695 \apidesc{Evaluates the predicate on the provided edge.}
696
697 \subsection{Class ParseCallback}
698
699 The ParseCallback class allows ParseAPI users to be notified of various events
700 during parsing. For most users this notification is unnecessary, and an
701 instantiation of the default ParseCallback can be passed to the CodeObject during initialization. Users who wish to be notified must implement a class that inherits from ParseCallback, and implement one or more of the methods described below to receive notification of those events.
702
703 \begin{apient}
704 struct default_details {
705     default_details(unsigned char*b,size_t s, bool ib) : ibuf(b), isize(s), isbranch(ib) { }
706     unsigned char * ibuf;
707     size_t isize;
708     bool isbranch;
709 }
710 \end{apient}
711 \apidesc{Details used in the \texttt{unresolved\_cf} and \texttt{abruptEnd\_cf}
712 callbacks.}
713
714 \begin{apient}
715 virtual void instruction_cb(Function*,Address,insn_details*)
716 \end{apient}
717 \apidesc{Invoked for each instruction decoded during parsing. Implementing this callback may incur significant overhead.}
718
719 \begin{apient}
720 struct insn_details {
721     InsnAdapter::InstructionAdapter * insn;
722 }
723 \end{apient}
724
725 \begin{apient}
726 void interproc_cf(Function*,Address,interproc_details*)
727 \end{apient}
728 \apidesc{Invoked for each interprocedural control flow instruction.}
729
730 \begin{apient}  
731 struct interproc_details {
732     typedef enum {
733         ret,
734         call,
735         branch_interproc, // tail calls, branches to plts
736         syscall
737     } type_t;
738     unsigned char * ibuf;
739     size_t isize;
740     type_t type;
741     union {
742         struct {
743             Address target;
744             bool absolute_address;
745             bool dynamic_call;
746         } call;
747     } data;
748 }
749 \end{apient}
750 \apidesc{Details used in the \texttt{interproc\_cf} callback.}
751
752 \begin{apient}
753 void overlapping_blocks(Block*,Block*)
754 \end{apient}
755 \apidesc{Noification of inconsistent parse data (overlapping blocks).}
756
757 \subsection{Containers}
758 \label{sec:containers}
759
760 Several of the ParseAPI data structures export containers of CFG objects; the
761 CodeObject provides a list of functions in the binary, for example, while
762 functions provide lists of blocks and so on. To avoid tying the internal
763 storage for these structures to any particular container type, ParseAPI objects
764 export a ContainerWrapper that provides an iterator interface to the internal
765 containers. These wrappers and predicate interfaces are designed to add minimal
766 overhead while protecting ParseAPI users from exposure to internal container
767 storage details. Users \emph{must not} rely on properties of the underlying
768 container type (e.g. storage order) unless that property is explicity stated in
769 this manual.
770
771 \noindent
772 ContainerWrapper containers export the following interface (\texttt{iterator} types vary depending on the template parameters of the ContainerWrapper, but are always instantiations of the PredicateIterator described below):
773
774 \begin{apient}
775 iterator begin()
776 iterator begin(predicate *)
777 \end{apient}
778 \apidesc{Return an iterator pointing to the beginning of the container, with or without a filtering predicate implementation (see Section \ref{sec:pred} for details on filter predicates).}
779
780 \begin{apient}
781 iterator const& end()
782 \end{apient}
783 \apidesc{Return the iterator pointing to the end of the container (past the last element).}
784
785 \begin{apient}
786 size_t size()
787 \end{apient}
788 \apidesc{Returns the number of elements in the container. Execution cost may vary depending on the underlying container type.}
789
790 \begin{apient}
791 bool empty()
792 \end{apient}
793 \apidesc{Indicates whether the container is empty or not.}
794
795 \noindent
796 The elements in ParseAPI containers can be accessed by iteration using an instantiation of the PredicateIterator. These iterators can optionally act as filters, evaluating a boolean predicate for each element and only returning those elements for which the predicate returns {\scshape true}. \emph{Iterators with non-{\scshape null} predicates may return fewer elements during iteration than their \texttt{size()} method indicates.} Currently PredicateIterators only support forward iteration. The operators \texttt{++} (prefix and postfix), \texttt{==}, \texttt{!=}, and \texttt{*} (dereference) are supported.
797
798
799 \appendix
800 \section{Extending ParseAPI}
801 \label{sec:extend}
802
803 The ParseAPI is design to be a low level toolkit for binary analysis tools.
804 Users can extend the ParseAPI in two ways: by extending the control flow
805 structures (Functions, Blocks, and Edges) to incorporate additional data to
806 support various analysis applications, and by adding additional binary code
807 sources that are unsupported by the default SymtabAPI-based code source. For
808 example, a code source that represents a program image in memory could be
809 implemented by fulfilling the CodeSource and InstructionSource interfaces
810 described in Section \ref{sec:codesource} and below. Implementations that
811 extend the CFG structures need only provide a custom allocation factory in
812 order for these objects to be allocated during parsing.
813
814 \subsection{Instruction and Code Sources}
815
816 A CodeSource, as described above, exports its own and the InstructionSource interface for access to binary code and other details. In addition to implementing the virtual methods in the CodeSource base class (Section \ref{sec:codesource}), the methods in the pure-virtual InstructionSource class must be implemented:
817
818 \begin{apient}
819 virtual bool isValidAddress(const Address) 
820 \end{apient}
821 \apidesc{Returns {\scshape true} if the address is a valid code location.}
822
823 \begin{apient}
824 virtual void* getPtrToInstruction(const Address)
825 \end{apient}
826 \apidesc{Returns pointer to raw memory in the binary at the provided address.}
827
828 \begin{apient}
829 virtual void* getPtrToData(const Address)
830 \end{apient}
831 \apidesc{Returns pointer to raw memory in the binary at the provided address. The address need not correspond to an executable code region.}
832
833 \begin{apient}
834 virtual unsigned int getAddressWidth()
835 \end{apient}
836 \apidesc{Returns the address width (e.g. four or eight bytes) for the represented binary.}
837
838 \begin{apient}
839 virtual bool isCode(const Address)
840 \end{apient}
841 \apidesc{Indicates whether the location is in a code region.}
842
843 \begin{apient}
844 virtual bool isData(const Address)
845 \end{apient}
846 \apidesc{Indicates whether the location is in a data region.}
847
848 \begin{apient}
849 virtual Address offset()
850 \end{apient}
851 \apidesc{The start of the region covered by this instruction source.}
852
853 \begin{apient}
854 virtual Address length()
855 \end{apient}
856 \apidesc{The size of the region.}
857
858 \begin{apient}
859 virtual Architecture getArch()
860 \end{apient}
861 \apidesc{The architecture of the instruction source. See the Dyninst manual for details on architecture differences.}
862
863 \begin{apient}
864 virtual bool isAligned(const Address)
865 \end{apient}
866 \apidesc{For fixed-width instruction architectures, must return {\scshape true} if the address is a valid instruction boundary and {\scshape false} otherwise; otherwise returns {\scshape true}. This method has a default implementation that should be sufficient.}
867
868 CodeSource implementors need to fill in several data structures in the base CodeSource class:
869
870 \begin{apient}
871 std::map<Address, std::string> _linkage
872 \end{apient}
873 \apidesc{Entries in the linkage map represent external linkage, e.g. the PLT in ELF binaries. Filling in this map is optional.}
874
875 \begin{apient}
876 Address _table_of_contents
877 \end{apient}
878 \apidesc{Many binary format have ``table of contents'' structures for position
879 independant references. If such a structure exists, its address should be filled in.}
880
881 \begin{apient}
882 std::vector<CodeRegion *> _regions
883 Dyninst::IBSTree<CodeRegion> _region_tree
884 \end{apient}
885 \apidesc{One or more contiguous regions of code or data in the binary object must be registered with the base class. Keeping these structures in sync is the responsibility of the implementing class.}
886
887 \begin{apient}
888 std::vector<Hint> _hints
889 \end{apient}
890 \apidesc{CodeSource implementors can supply a set of Hint objects describing where functions are known to start in the binary. These hints are used to seed the parsing algorithm. Refer to the CodeSource header file for implementation details.}
891
892 \subsection{CFG Object Factories}
893 \label{sec:factories}
894
895 Users who which to incorporate the ParseAPI into large projects may need to store additional information about CFG objects like Functions, Blocks, and Edges. The simplest way to associate the ParseAPI-level CFG representation with higher-level implementation is to extend the CFG classes provided as part of the ParseAPI. Because the parser itself does not know how to construct such extended types, implementors must provide an implementation of the CFGFactory that is specialized for their CFG classes. The CFGFactory exports the following simple interface:
896
897 \begin{apient}
898 virtual Function * mkfunc(Address addr, 
899     FuncSource src,
900     std::string name, 
901     CodeObject * obj, 
902     CodeRegion * region,
903     Dyninst::InstructionSource * isrc)
904 \end{apient}
905 \apidesc{Returns an object derived from Function as though the provided parameters had been passed to the Function constructor. The ParseAPI parser will never invoke \texttt{mkfunc()} twice with identical \texttt{addr}, and \texttt{region} parameters---that is, Functions are guaranteed to be unique by address within a region.}
906
907 \begin{apient}
908 virtual Block * mkblock(Function * func, CodeRegion * region, Address addr)
909 \end{apient}
910 \apidesc{Returns an object derived from Block as though the provided parameters had been passed to the Block constructor. The parser will never invoke \texttt{mkblock()} with identical \texttt{addr} and \texttt{region} parameters.}
911
912 \begin{apient}
913 virtual Edge * mkedge(Block * src, Block * trg, EdgeTypeEnum type)
914 \end{apient}
915 \apidesc{Returns an object derived from Edge as though the provided parameters had been passed to the Edge constructor. The parser \emph{may} invoke \texttt{mkedge()} multiple times with identical parameters.}
916
917 \begin{apient}
918 virtual Block * mksink(CodeObject *obj, CodeRegion *r)
919 \end{apient}
920 \apidesc{Returns a ``sink'' block derived from Block to which all unresolvable control flow instructions will be linked. Implementors may return a unique sink block per CodeObject or a single global sink.}
921
922 Implementors of extended CFG classes are required to override the default implementations of the \emph{mk*} functions to allocate and return the appropriate derived types statically cast to the base type. Implementors must also add all allocated objects to the following internal lists:
923
924 \begin{apient}
925 fact_list<Edge> edges_
926 fact_list<Block> blocks_
927 fact_list<Function> funcs_
928 \end{apient}
929 \apidesc{O(1) allocation lists for CFG types. See the CFG.h header file for list insertion and removal operations.}
930
931 Implementors \emph{may} but are \emph{not required to} override the
932 deallocation following deallocation routines. The primary reason to override
933 these routines is if additional action or cleanup is necessary upon CFG object
934 release; the default routines simply remove the objects from the allocation
935 list and invoke their destructors.
936
937 \begin{apient}
938 virtual void free_func(Function * f)
939 virtual void free_block(Block * b)
940 virtual void free_edge(Edge * e)
941 virtual void free_all()
942 \end{apient}
943 \apidesc{CFG objects should be freed using these functions, rather than delete, to avoid leaking memory.}
944
945 \section{Defensive Mode Parsing}
946 \label{sec:defmode}
947
948 Binary code that defends itself against analysis may violate the
949 assumptions made by the the ParseAPI's standard parsing algorithm.
950 Enabling defensive mode parsing activates more conservative
951 assumptions that substantially reduce the percentage of code that is
952 analyzed by the ParseAPI.  For this reason, defensive mode parsing is
953 best-suited for use of ParseAPI in conjunction with dynamic analysis
954 techniques that can compensate for its limited coverage of the binary
955 code.  This mode of parsing will be brought to full functionality in 
956 an upcoming release.  
957
958 \end{document}