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