exploitation.xml
No OneTemporary

File Metadata

Created
Thu, Jul 9, 7:27 AM

exploitation.xml

<?xml version="1.0" encoding="UTF-8"?>
<chapter version="5.1" xmlns="http://docbook.org/ns/docbook"
xmlns:xlink="http://www.w3.org/1999/xlink"
xmlns:xila="http://www.w3.org/2001/XInclude/local-attributes"
xmlns:xi="http://www.w3.org/2001/XInclude"
xmlns:trans="http://docbook.org/ns/transclusion"
xmlns:svg="http://www.w3.org/2000/svg"
xmlns:m="http://www.w3.org/1998/Math/MathML"
xmlns:html="http://www.w3.org/1999/xhtml"
xmlns:db="http://docbook.org/ns/docbook">
<?xxe-sn 26yv439af40 1?>
<title><?xxe-sn 26yv439af40 2?>Exploitation</title>
<para><?xxe-sn 26yv439af40 6?>This chapter discusses <emphasis><?xxe-sn 26yv439af40 7?>exploiting</emphasis>
external resources, such as files, as a particular instance of a
<emphasis><?xxe-sn 26yv439af40 8?>side effects</emphasis> problem that
inevitably stems from an interaction with the outside world. Unlike <link
xlink:href="/w/virtualization"><?xxe-sn 295bzzou9kw 2?>virtualization</link>,
an another documentation's topic that tackles I/O, exploitation approaches
subject from a different angle — it is concerned with an <emphasis><?xxe-sn 26yv439af40 x?>order
of operations</emphasis>, sequence in which different clients jointly use
the same resource and it deals with corresponding difficulties, e.g. ensures
proper resource initialization before actual usage.</para>
<section>
<?xxe-sn 29je46abuev -wunr7fl0rw8v?>
<title><?xxe-sn 29je46abuev -wunr7fl0rw8u?>Syntax</title>
<section>
<?xxe-sn 29je46abuev -wunr7fl0rw8s?>
<title><?xxe-sn 29je46abuev -wunr7fl0rw8r?>Annotations</title>
<synopsis><?xxe-sn 29je46abuev -wunr7fl0rw8q?>SYNTAX:
**use**(//resource-id//)
**init**(//resource-id//)</synopsis>
<itemizedlist>
<?xxe-sn 29je46abuev -wunr7fl0rw8p?>
<listitem>
<?xxe-sn 29je46abuev -wunr7fl0rw8o?>
<para><?xxe-sn 29je46abuev -wunr7fl0rw8n?><emphasis><?xxe-sn 29je46abuev -wunr7fl0rw8m?>resource-id</emphasis>
— user-defined resource identifier</para>
</listitem>
</itemizedlist>
<para><?xxe-sn 29je46abuev -wunr7fl0rw8l?>Annotates function or code
block as such that exploits resource <emphasis><?xxe-sn 29je46abuev -wunr7fl0rw8k?>resource-id</emphasis>.</para>
</section>
<section>
<?xxe-sn 29je46abuev -wunr7fl0rw8j?>
<title><?xxe-sn 29je46abuev -wunr7fl0rw8i?>Guards</title>
<synopsis><?xxe-sn 29je46abuev -wunr7fl0rw8h?>SYNTAX:
**exploitation(init)**
**exploitation(none)**</synopsis>
<para><?xxe-sn 29je46abuev -wunr7fl0rw8g?>Specializations that are
recognized by exploitation reasoning. Each specialization corresponds to
an initialization strategy:</para>
<itemizedlist>
<?xxe-sn 29je46abuev -wunr7fl0rw8f?>
<listitem>
<?xxe-sn 29je46abuev -wunr7fl0rw8e?>
<para><?xxe-sn 29je46abuev -wunr7fl0rw8d?><code><?xxe-sn 29je46abuev -wunr7fl0rw8a?>exploitation(init)</code>
is expected to perform actual resource initialization.</para>
</listitem>
<listitem>
<?xxe-sn 29je46abuev -wunr7fl0rw8c?>
<para><?xxe-sn 29je46abuev -wunr7fl0rw8b?><code><?xxe-sn 29je46abuev -wunr7fl0rw89?>exploitation(none)</code>
is expected to do nothing as initialization isn't necessary or done
elsewhere.</para>
</listitem>
</itemizedlist>
</section>
</section>
<section>
<?xxe-sn 26yv439af40 3?>
<title><?xxe-sn 26yv439af40 4?>Background</title>
<para><?xxe-sn 26yv439af40 b?>In software engineering, the idea to avoid
side effects have received considerable traction. Indeed, side effects is
something that is hard to take into account and thus programs that have
side effects are inherently unsafe, thus best coding practices are
rightfully suggest to isolate side effects producing code as much as
possible. It's so called pure functional languages whose philosophy goes
even further and frames side effects as something opposite of "pure", and
everything is built around effectless computations to the point that some
languages' design itself includes side effects producing constructs, such
as I/O, as an afterthought, as something almost unnecessary.</para>
<para><?xxe-sn 26yv439af40 c?>However, in reality the opposite is true,
most applications' sole responsibility is to communicate with "outside
world", reacting to the external events and change "world state"
accordingly. As a consequence, side effects usually are the
<emphasis><?xxe-sn 26yv439af40 d?>only</emphasis> important effects the
program produce and surely deserve first class support from a programming
language and justify efforts to develop approach to alleviate related
safety and performance concerns.</para>
</section>
<section>
<?xxe-sn 26yv439af40 z?>
<title><?xxe-sn 26yv439af40 10?>Exploitation Plan</title>
<para><?xxe-sn 26yv439af40 12?>One complexity of taking side effects into
account is the fact that final result depends on an <emphasis><?xxe-sn 28ivhnywem8 1?>exact
operations order</emphasis>. This harshly impacts both performance and
safety, for many techniques, e.g. caching, parallelization can neither be
automatically performed nor validated since they are based on various
degrees of reordering or deal with possibly undetermined beforehand order
of execution.</para>
<para><?xxe-sn 28ivhnywem8 2?>In this chapter, it is assumed, that final
effects of execution fully defined by <emphasis><?xxe-sn 28ivhnywem8 3?>exploitation
path</emphasis> — for a particular code path that can occur during
execution, it is its part consisting of only relevant code blocks., i.e.
those that deal with an exploited resource. Other code blocks do not
influence exploitation effects and so are excluded from consideration.
Thus reasoning about effects is reduced to considering all possible
exploitation paths, checking do they meet certain requirements that define
valid exploitation and making corrections if needed and possible.</para>
<para><?xxe-sn 26yv439af40 13?>Result of the reasoning is called
<emphasis><?xxe-sn 26yv439af40 14?>exploitation plan</emphasis> —
specification that defines exact order and strategy of using a given
resource in order to comply with imposed requirements.</para>
<para><?xxe-sn 26yv439af40 15?>With all above said, the discussed approach
can be presented as follows:</para>
<itemizedlist>
<?xxe-sn 26yv439af40 16?>
<listitem>
<?xxe-sn 26yv439af40 17?>
<para><?xxe-sn 26yv439af40 18?>Annotations are used to express some
aspects of side effects to enable further reasoning. They indicate
code blocks that deal with resource as well as provide additional
information about how exactly it is exploited, e.g. use, initialize or
deinitialize resource.</para>
</listitem>
<listitem>
<?xxe-sn 28ivhnywem8 4?>
<para><?xxe-sn 28ivhnywem8 5?>Existing code paths, extracted during
source code processing, coupled with relevant annotations is enough to
construct all possible exploitation paths and analyze them. Analysis
determines possible(<emphasis><?xxe-sn 295bzzou9kw 3?>weak</emphasis>)
paths that can occur or not during particular execution as well as
certain paths(<emphasis><?xxe-sn 295bzzou9kw 4?>strong</emphasis>)
that occur always no matter what. Also it checks are exploitation
paths valid against certain rules, e.g. initialization occurs always
before actual usage and is it possible to correct invalid
paths.</para>
</listitem>
<listitem>
<?xxe-sn 28ivhnywem8 6?>
<para><?xxe-sn 28ivhnywem8 7?>Reasoning's result is an exploitation
plan that dictates order and strategy of exploitation is presented in
form of appropriate specialization for polymorphic functions that deal
with resources in order to ensure safe exploitation to the extent
based on provided annotations.</para>
</listitem>
<listitem>
<?xxe-sn 26yv439af40 19?>
<para><?xxe-sn 26yv439af40 1a?>Exploitation related side effects are
viewed as a set of additional restrictions over operations order. Only
subset of possible reorders is still valid w.r.t. side effects.
Transcend's task is to find out refined set of valid orders. Thus
techniques that rely on reordering enjoy additional information to
make safe optimizations.</para>
</listitem>
</itemizedlist>
<para><?xxe-sn 26yv439af40 1b?>... and it serves three major goals:</para>
<itemizedlist>
<?xxe-sn 26yv439af40 1c?>
<listitem>
<?xxe-sn 26yv439af40 1d?>
<para><?xxe-sn 26yv439af40 1e?>Safety. Validates existing exploitation
plan or is it possible to safely exploit given resource at all.
Compiler signals error if a given exploitation plan is invalid, i.e.
does not satisfy requirements w.r.t. side effects as expressed by
annotations.</para>
</listitem>
<listitem>
<?xxe-sn 28j5661y0mv -wunr7fl0rw8v?>
<para><?xxe-sn 28j5661y0mv -wunr7fl0rw8u?>Regression Resilience. When
it comes to using external resources, some spurious dependencies
usually occur between otherwise isolated, independent components of a
program. Sometimes refactoring and other code changes break those
dependencies inevitably introducing regressions. Exploitation catches
this sort of regressions and automatically regenerates exploitation
plan suited for a changed conditions.</para>
</listitem>
<listitem>
<?xxe-sn 26yv439af40 1f?>
<para><?xxe-sn 26yv439af40 1g?>Performance. Generated exploitation
plans are optimal in a sense that they cut off superfluous operations,
for example, removing resource initialization in several places if it
can be done safely in a single one, thus reducing overall
overhead.</para>
</listitem>
</itemizedlist>
</section>
<section>
<?xxe-sn 27ay8x1a5mo 1?>
<title><?xxe-sn 27ay8x1a5mo 2?>Domination Analysis</title>
<para><?xxe-sn 27ay8x1a5mo 3?>When it comes to a reasoning about order of
execution flow and possible code paths, crucial vehicle for that is
<emphasis><?xxe-sn 27ay8x1a5mo 4?>domination analysis</emphasis> producing
<emphasis><?xxe-sn 27ay8x1a5mo 5?>dominator tree</emphasis> as an
output.</para>
<para><?xxe-sn 27ay8x1a5mo 6?>Unlike the usual function-bounded domination
analysis, when separate domination tree is produced for each function
defined in a program, Exploitation requires program bound analysis, that
is to take into account control flow across all functions in a program. It
is computationally intensive task to perform analysis over a whole
program, however it is compensated by the fact that Exploitation only
takes into account code blocks that deal with, or in other words, exploit
external resources. Thus there is no necessity to build full dominator
tree, only the relevant parts are constructed, just enough to make sound
exploitation plan decisions.</para>
</section>
<section>
<?xxe-sn 28h47d43thc i?>
<title><?xxe-sn 28h47d43thc j?>Empty Exploitation Plan. Effect Free
Computations</title>
<para><?xxe-sn 28h47d43thc k?>Validation of exploitation path is done
against some predefined constraints. Depending on complexity of a
constraints, i.e. number of different exploitation events that are seeking
for in each path, reasoning goals categorized into several groups:</para>
<itemizedlist>
<?xxe-sn 28j5661y0mv -wunr7fl0rw8t?>
<listitem>
<?xxe-sn 28j5661y0mv -wunr7fl0rw8s?>
<para><?xxe-sn 28j5661y0mv -wunr7fl0rw8r?>Zero Order Exploitation.
Meaning that all paths are checked in terms is there exploitation at
all or no, is there at least a single exploitation event along the
path.</para>
</listitem>
<listitem>
<?xxe-sn 28j5661y0mv -wunr7fl0rw8q?>
<para><?xxe-sn 28j5661y0mv -wunr7fl0rw8p?>First Order Exploitation.
Deals with a situations when it's enough to check only two different
exploitation event occur in a required order. It can be useful for
example, to check whether all resource uses occur after it is
initialized.</para>
</listitem>
<listitem>
<?xxe-sn 28j5661y0mv -wunr7fl0rw8o?>
<para><?xxe-sn 28j5661y0mv -wunr7fl0rw8n?>Higher Order Exploitation.
Expresses constraints involving several(more than two) exploitation
events and relations between them.</para>
</listitem>
</itemizedlist>
<para><?xxe-sn 28j5661y0mv -wunr7fl0rw8m?><emphasis><?xxe-sn 28j5661y0mv -wunr7fl0rw8l?>Empty
Exploitation</emphasis> is an important instance of zero order constraint.
It useful mechanism for developer to annotate function or part of a
program as effect free in terms of exploitation. Thus, efectless, clean or
pure code can be clearly separated from effectfull part and compiler
raises compilation error in case of accidental mixing or using "wrong"
type of code in non appropriate environment.</para>
</section>
<section>
<?xxe-sn 26yv439af40 u?>
<title><?xxe-sn 26yv439af40 v?>Resource Initialization</title>
<para><?xxe-sn 26yv439af40 w?>One important problem related to an
exploitation order is to ensure that a given resource is properly
initialized before its first usage and additionally it is not initialized
more then once during exploitation session. This is instance of first
order exploitation since in a validation mode it is enough to check
exploitation plan to ensure that every resource usage preceded by resource
initialization at some point in the <emphasis><?xxe-sn 28jw0wb6fpc 1?>past</emphasis>,
i.e. previously in the exploitation path.</para>
<para><?xxe-sn 28jw0wb6fpc 2?>For planning mode, the problem is addressed
as follows:</para>
<itemizedlist>
<?xxe-sn 28jw0wb6fpc 3?>
<listitem>
<?xxe-sn 28jw0wb6fpc 4?>
<para><?xxe-sn 28jw0wb6fpc 5?>Central idea of the algorithm is to
consider candidates for initialization only among code blocks that
<emphasis><?xxe-sn 295bzzou9kw 5?>dominate</emphasis> given usage
site. Obviously, initialization in dominating block precedes usage for
any possible code path.</para>
</listitem>
<listitem>
<?xxe-sn 295bzzou9kw 6?>
<para><?xxe-sn 295bzzou9kw 7?>One or more dominator blocks are chosen
for actual initialization in such way that they are cover all found
usage sites.</para>
</listitem>
<listitem>
<?xxe-sn 295bzzou9kw 8?>
<para><?xxe-sn 295bzzou9kw 9?>For code blocks chosen for
initialization specialization <code><?xxe-sn 295bzzou9kw a?>exploitation(init)</code>
is set, for the rest specialization <code><?xxe-sn 295bzzou9kw b?>exploitation(none)</code>
is used.</para>
</listitem>
</itemizedlist>
<para><?xxe-sn 28h47d43thc 1?>Look at the example below:</para>
<programlisting xml:id="ResourceInit_1"><?xxe-sn 28h47d43thc 2?>name="tests/exploitation.cpp: Doc_ResourceInit_1", lines=15
import raw("scripts/cfa/payload.lp").
import raw("scripts/exploitation/exploitation.lp"). //exploitation reasoning
import raw("scripts/exploitation/test1.assembly.lp").
guard:: exploitation(init)
{
openFile = function(filePrev:: FILE_P):: FILE_P; init(file)
{
fopen("/tmp/test", "w")::FILE_P
}
}
guard:: exploitation(none)
{
openFile = function(filePrev:: FILE_P):: FILE_P
{
filePrev::int
}
}
test = function:: int; entry
{
seq
{ f0 = undef:: FILE_P. f0 }
{
//Scope #1:
f1 = openFile(f0):: FILE_P.
f1
}
{ //Scope #2:
f2 = openFile(f1):: FILE_P.
f2
}
{
//Scope #3:
sizeWritten = fwrite("Attempt to write..", 12, 1, f2):: int; use(file).
sizeWritten
}
{
//Scope #4:
fclose(f2):: int; use(file)
}
{ sizeWritten :: int}
}</programlisting>
<para><?xxe-sn 28h47d43thc 3?>There is the function <code><?xxe-sn 28h47d43thc 4?>test</code>
that executes sequentially next commands: open a file(scopes #1, #2),
write some text(scope #3) and finally, close the file(scope #4). It
represents simple work flow with an external resource.</para>
<para><?xxe-sn 28h47d43thc 7?>In order to connect the code to the
exploitation the functions <code><?xxe-sn 28h47d43thc 5?>fwrite</code> and
<code><?xxe-sn 28h47d43thc 6?>fclose</code> in scopes #3 and #4
respectively are annotated with annotation <code><?xxe-sn 295bzzou9kw c?>use(file)</code>.
This information is used by reasoning to look whether it is possible to
initialize given resource before actual usage as well as where and when
exactly to initialize it. Function <code><?xxe-sn 28h47d43thc 9?>openFile</code>
is annotated as <code><?xxe-sn 28h47d43thc a?>init(file)</code> meaning it
<emphasis><?xxe-sn 28h47d43thc b?>can</emphasis> initialize depending on
chosen strategy. The function is invoked both in scope #1 and scope #2.
Both scopes are executed <emphasis><?xxe-sn 28h47d43thc d?>strictly
before</emphasis> scopes #3, #4. Thus it is indeed possible to initialize
resource before usage. Next task for exploitation is to choose correct
exploitation plan, i.e. to assign strategies for all possible
initialization places in the effort to initialize resource only once.
Here, it means that only one invocation of <code><?xxe-sn 28h47d43thc e?>openFile</code>
is assigned with <code><?xxe-sn 28h47d43thc f?>exploitation(init)</code>
to actually initialize the file. Other one is automatically marked with
<code><?xxe-sn 28h47d43thc g?>exploitation(none)</code> to invoke
different specialization of <code><?xxe-sn 28h47d43thc h?>openFile</code>
that does nothing since the files is already initialized.</para>
</section>
</chapter>
<?xxe-revisions
#12 2019-02-09T15:16:04Z pgess
#11 2019-02-02T13:07:26Z pgess
1sPEAAABgYUIAAyBhQgAAAQBc4GFCAA=
#10 2019-02-01T17:38:23Z pgess
1sPEAAABgYUKAIFE9icACGZQc28yPz5sZWFziRsTC0MIQ2oTC2OCNgECQ4MkU4s0IwcTC2PCVFMF
MyRTFgEDM4kVEwVDCmMJU4I8EwxThHozgVuDDEOBGoMIMwljVVMMQwVTPBMEAQMTBxMGYw5TbUMP
Yx9TLHMQEwcTChMJUxYAiR6YbxmDNI5ygjqDMb5tjjuLSbZOimemdYERpyObYagAiSKDYoJMhH3i
gWejny2BIIFcqCZl6Q6TG4l51AGZa4N5lkeBJZzSBZdFigWdWA==
#9 2019-01-26T14:30:18Z pgess
1sPEAAAB9icAUfYlAAEqIGRz0wATB0OBHVMEQxszCBMFQzRTBTMEYwdjgRgTCAEBY4I9MwpDgVxj
m00Ap2mrJoRxiR2ZGo5OijKLeq8mnUlJhCOBG54rgkGBYw==
#8 2019-01-15T20:23:54Z pgess
1sPEAAAB9ioAhCvvEAAlgiWBWTphc3NvY+KAlENzVW5ld2Jyb2tld2lmb3JzIDh0cmlnZ2MzZWRz
hjUTDkNNEwgjBVMPAQFDQVNUAQVjBCMHMwQTBjMIY4wxUwdDgw5jfwEDUwQzihsBAVMiIwVjgRFD
BFNTYwYzgnoTByMGAQFDix3UEwxDCjMGMwxjBVM2YxozBc0TBkMWEyBjbFMJUyVjDhMIMzdji11T
CEMHMxVTBwEFYwSkY4I8kxZTK2OLHFMYM1EBAjOBEhMRUw0TEEOBPUMdMwSTCDMFUwlDBwEEYxET
CUMMUyAzim8zEUMcYwVTIRMSQxozgV1TEZMLAQFjE2MKEwcBBTMEgwxjC1MGYwQzBjMOQ4EbM4FY
UwkTBGMXAQFTD0MIUw5jTSMEEwtTBwEBUwczGpMIQwgzBVMGAQJjgQYTBTMFkwhjBmMHcwVTCYME
UwQzCUODSwCGSj+FZK15XBNPiyyLPJR1hWWUNYNkpX6MOIMfiRmBCIolnGArgTQQdhKbF60ngxKE
KINihiyoLp1okBUHN4hQjnyjB404oSOUH4lodqw8hHBFO4ZOqxeLbIIllBGGCCpGrHyDDC6HLFip
eZ4Bg3iBQYFqhwi+jEQfpVuYPIl8mXqLN4dsin4bj20rhGeZD0++OQWCBYFdllSWf+JYhH8Oymig
CB+BHoFDok6fa5MkgieFGRKBGqJyzHaLRL41cCiqf69yhAWEe4FAcM5PhGACnnsZgT6gNho=
#7 2019-01-15T13:53:13Z pgess
1sPEAAAB7xAAIuoxAAAQDHPREhMKQwRTQBMJExBjmDgAog2uVjCJF4N4hUU=
#6 2019-01-15T11:27:29Z pgess
1sPEAAAB6jIAF+dpAAAKB3PMJBMJQylTmxMAiReKLbtb
#5 2019-01-15T08:04:19Z pgess
1sPEAAAB520AglrYYQAogTF6RGF0aXNvZmluIGxpbVN0bDo6IEMxakRlLCwsaGxsIEluIHNoYWJ1
dHOjSwEDEwYBAiMEAQJDCmMEYwtDTGMFUyIzBzMGEw9TgyxDDxMFYwYTCSMFIwoTBTMKEwkzJgEG
MwQzC1OCV+ETBQEBQ1pjCVMMM0djBgEBY4EBAQFDJVMxEwZjdxMMQy4BA1MJYxJjFjMgYwQTGwEC
YxkBAUMGAQFjBFMGAQODCZMMgywBATMIMwQBBkMEExL5EwdDC0MHYxJDBQECUwSDCVOGCQEDQ4Na
gwkzKVObEwCRFaoCiCekAopDFIULT3MjmUcbgweMEYRHhjqtBLRjhWyRCoRwkXWCKoEaPYFqh32C
W4EahyZxhydMgQJfnjBHgzSFHYs5rTyVBJE+oEODeJFFjn6SK50Al37CmTiVDYJ8kR9Wi06ZMoMu
EoEUnUCXizOGEJeKLY5K
#4 2019-01-14T13:48:02Z pgess
1sPEAAAB2GUAgSjKVwAOVz0zPz5UdHRlc2hvdWxTcnOVKhMWQ4IsEwzdUwUBAWMEUwdjCGMJIwYB
ATMFAQFjBFMIEx9TNVMEMwRjC1MMUxEBBRMEMwkzgl5TCmMLgyBDIwEBY4FMMw0zBFMXM4pXEwUB
AWOgfQCVTSKDNKlVixtjgU2UA4k+mUicDoljFoQumTyORYVtRoN7HZdigjEdkjOBQiyJVjmVRIRC
gQeCUZlRh2Q=
#3 2018-12-24T11:55:39Z pgess
1sPEAAAByiAAglmxQABBgSBxZmxmbWZucmVzdWxpbmRpdmlkZG8gc28sIGJvZ3VzIGdsb2JpcyBs
bCBsQ0ZHNz8+QS04Pz5mb3J3bzk/PnAvPgpzpUkTCwECQx8BAlMZUyUBAmMpM4EjU4IUYwgBBRMF
Mw4TBhMJQwcBB2MMMwQTC0MgMwYzByMPQyVDCwERYwRDBRMFYwUzBEMJUwQTBAEDEwQzB+LWUw4B
A0MKExBzCwEEUwUzBiMMAQEzCFMKYwQTF3MLAQczBFMHAQFDDTMGExRzCwEEQwSDByMPUwRDBRMF
Qw1TKWOCS3MLAQETCAECAIM0DKp5LlmhW4E7gxWgXIJenROObIhji1uHGoNjOIxDiwt0S5NdhiSN
F4xGlnaRBothlSWICkSYHIYbimyXV4I3g3jJhQKEEIIQi1uDJJ8LhCvJjEOBfINCl0GELsmHL8VC
hTySPYYHhl2NPYcQxAE=
#2 2018-12-24T11:20:18Z pgess
1sPEAAABsUAAErE4AAAHBXOwUxMGQ18AqheGSg==
#1 2018-12-18T16:02:30Z pgess
1sPEAAABsT0AMqdsAAIYEm9sc6JqAQITDEMLQwuDIDODMhMLQ2JDFGMLAJhklUuCMJSIGoM0izSB
dIJQ
?>

Event Timeline