SBLP - CBSoft 2013 - Universidade de Brasília

Transcrição

Congresso Brasileiro de Software: Teoria e Prática
29 de setembro a 04 de outubro de 2013
Brasília-DF
Anais
SBLP 2013
XVII Simpósio Brasileiro de Linguagens de Programação
SBLP 2013
XVII Simpósio Brasileiro de Linguagens de Programação
03 e 04 de outubro de 2013
Brasília-DF, Brasil
ANAIS
Volume 01
ISSN: 2175-5922
Coordenadores do Comitê de Programa do SBLP 2013
André Rauber Du Bois
Phil Trinder
COORDENAÇÃO DO CBSOFT 2013
Genaína Rodrigues – UnB
Rodrigo Bonifácio – UnB
Edna Dias Canedo - UnB
Realização
Universidade de Brasília (UnB)
Departamento de Ciência da Computação (DIMAp/UFRN)
Promoção
Sociedade Brasileira de Computação (SBC)
Patrocínio
CAPES, CNPq, Google, INES, Ministério da Ciência, Tecnologia e Inovação, Ministério do Planejamento, Orçamento e Gestão e RNP
Apoio
Instituto Federal Brasília, Instituto Federal Goiás, Loop Engenharia de Computação, Secretaria de Turismo
do GDF, Secretaria de Ciência Tecnologia e Inovação do GDF e Secretaria da Mulher do GDF
SBLP 2013
17th Brazilian Symposium on Programming Languages
October 3 to 4, 2013
Brasília-DF, Brazil
PROCEEDINGS
Volume 01
ISSN: 2175-5922
SBLP 2013 Program Committee Chairs
Phil Trinder
CBSOFT 2013 gENERAL CHAIRS
Genaína Rodrigues – UnB
Rodrigo Bonifácio – UnB
Edna Dias Canedo - UnB
ORGANIZATION
Universidade de Brasília (UnB)
Departamento de Ciência da Computação (DIMAp/UFRN)
PROMOTION
Brazilian Computing Society (SBC)
SPONSORS
CAPES, CNPq, Google, INES, Ministério da Ciência, Tecnologia e Inovação, Ministério do Planejamento, Orçamento e Gestão e RNP
SUPPORT
Instituto Federal Brasília, Instituto Federal Goiás, Loop Engenharia de Computação, Secretaria de Turismo
do GDF, Secretaria de Ciência Tecnologia e Inovação do GDF e Secretaria da Mulher do GDF
Autorizo a reprodução parcial ou total desta obra, para fins acadêmicos, desde que citada a fonte
SBLP 2013
foreword
The Brazilian Symposium on Programming Languages (SBLP) is a series of annual conferences
promoted by the Brazilian Computer Society (SBC) since 1996. In the last four years, it has been
organized in the context of CBSoft (Brazilian Conference on Software: Theory and Practice), co-located
with a number of other events on computer science and software engineering.
SBLP 2013 is the 17th edition of the Symposium, and was held in Brasília, Brazil, organized by the
Department of Computer Science of the University of Brasília (UnB). It was collocated with the 2013
editions of SBMF (Brazilian Symposium on Formal Methods), SBES (Brazilian Symposium on Software
Engineering), and SBCARS (Brazilian Symposium on Software Components, Architecture and Reuse),
under CBSoft 2013. The previous editions of SBLP were held in Natal (2012), São Paulo (2011), Salvador
(2010), Gramado (2009), Fortaleza (2008), Natal (2007), Itatiaia (2006), Recife (2005), Niterói (2004),
Ouro Preto (2003), Rio de Janeiro (2002), Curitiba (2001), Recife (2000), Porto Alegre (1999), Campinas
(1997), and Belo Horizonte (1996).
The Program Committee (PC) of SBLP 2013 comprised 36 members, from 8 countries. SBLP 2013
received 31 submissions, including 4 short papers, with authors from Argentina, Brazil, Mexico,
The Netherlands, Portugal, USA, and Uruguay. Each paper was reviewed by at least four reviewers,
including 14 reviewers outside the PC. The referee reports were discussed by the reviewers, generally
leading to a consensus. The final selection was made by the Program Committee Co-chairs, based
on the reviews and programme committee discussion. As in previous editions, the authors of the 10
full papers selected will be invited to submit extended versions of their works to be considered for
publication in a special issue of a reputed journal in computer science. The technical program of SBLP
2013 also included keynote talks from Tim Harris (Oracle Labs, UK), and Ryan R. Newton (Indiana
University).
We would like to thank the referees for their reviews, the members of the PC for their reviews and
contributions to the discussion and decision-making, and the invited speakers for accepting our
invitation and enriching the technical program with interesting talks. We also thank the authors, the
sponsors, and the Organizing Committee of CBSoft 2013 for contributing to the success of SBLP 2013.
Phil Trinder
5
SBLP 2013
Program Committee Chairs Short
Biographies
André Rauber Du Bois is an adjunct professor at the Computer Science Department of the Federal
University of Pelotas (UFPel). He obtained his doctoral degree in the Department of Mathematical and
Computer Sciences at Heriot-Watt University, UK. His Resarch interests include parallel and distributed
functional languages, transactional memory, semantics and mobile computing.
Phil Trinder
Professor Phil Trinder has been an active researcher in parallel and distributed technologies for over
20 years. He has been an investigator on 13 research projects (Principle Investigator on 10), with the
projects primarily funded by the EU or the UK’s Engineering and Physical Sciences Research Council
(EPSRC). Professor Trinder holds a DPhil from Oxford University and has over 100 publications in
journals, books, or refereed conferences.
Professor Trinder’s key research interest is in designing, implementing, and evaluating high-level
distributed and parallel programming models. He has an extensive record of collaborating with both
academic and industrial partners, and examples of the latter include long term relationships with
Ericsson, Maplesoft, Microsoft UK Research Labs, and Motorola.
6
SBLP 2013
Comitês Técnicos / Technical Committees
Comitê Diretivo/Steering Committee
Francisco Heron de Carvalho Junior, UFC, Brazil
Christiano Braga, UFF, Brazil
Ricardo Massa Ferreira Lima, UFPE, Brazil
André Rauber Du Bois, UFPel, Brazil
Comitê de Programa / Program Committee
Alberto Pardo, Universidad de La República, Uruguay
Alex Garcia, IME, Brazil
Álvaro Freitas Moreira, UFRGS, Brazil
André Santos, UFPE, Brazil
Carlos Camarão, UFMG, Brazil
Christiano Braga, UFF, Brazil
Edwin Brady, University of St. Andrews, UK
Fernando Castor Filho, UFPE, Brazil
Fernando Quintão Pereira, UFMG, Brazil
Francisco H. de Carvalho Junior, UFC, Brazil
Hans-Wofgang Loidl, Heriot-Watt University, UK
Jeremy Singer, Glasgow University, UK
João Saraiva, Universidade do Minho, Portugal
João F. Ferreira, Teesside University, UK
Lucilia Figueiredo, UFOP, Brazil
Luis Soares Barbosa, Universidade do Minho, Portugal
Manuel António Martins, Universidade de Aveiro, Portugal
Marcelo A. Maia, UFU, Brazil
Marcello Bonsangue, Leiden University/CWI, The Netherlands
Marcelo d’Amorim, UFPE, Brazil
Marco Tulio Valente, UFMG, Brazil
Mariza A. S. Bigonha, UFMG, Brazil
Martin A. Musicante, UFRN, Brazil
Noemi Rodriguez, PUC-Rio, Brazil
Peter Mosses, Swansea University, UK
Zongyan Qiu, Pekin University, China
Rafael Dueire Lins, UFPE, Brazil
Ricardo Massa, UFPE, Brazil
Roberto S. Bigonha, UFMG, Brazil
Roberto Ierusalimschy PUC-Rio, Brazil
Sandro Rigo, UNICAMP, Brazil
Sergio Soares, UFPE, Brazil
Simon Thompson, University of Kent, UK
Varmo Vene, University of Tartu, Estonia
7
SBLP 2013
Revisores Adicionais /Additional Referees
A. Annamaa
J. Cunha
C. de Faveri
J. P. Fernandes
R. Ferreira
M. Garcia
F. Medeiros Neto
H. Nestra
R. Neves
E. Piveta
A. Rademaker
P. Torrini
M. Viera
V. Vojdani
Palestras convidadas / invited keynotes
Big-Tent Deterministic Parallelism
Ryan R. Newton, Indiana University, USA
Nondeterminism is essential for achieving flexible parallelism: it allows tasks to be scheduled onto
cores dynamically, in response to the vagaries of an execution. But if schedule nondeterminism is
observable within a program, it becomes much more difficult for programmers to discover and correct
bugs by testing, let alone to reason about their programs in the first place. While much work has
focused on identifying methods of deterministic parallel programming, guaranteed determinism in
real parallel programs remains a lofty and rarely achieved goal. It places stringent constraints on the
programming model: concurrent tasks must communicate in restricted ways that prevent them from
observing the effects of scheduling, a restriction that must be enforced at the language or runtime
level.
This talk will overview the known forms of deterministic-by-construction parallel languages, including:
Kahn process networks, pure data-parallelism, single assignment languages, functional programming,
and type-effect systems that enforce limited access to state by threads. However, I will argue that
existing approaches remain fragmented and under-exploited, and that an effort is called for both to
extend the scope of deterministic approaches and to better integrate known approaches. The ultimate
target is a full-featured programming environment that enables a practical form of guaranteeddeterministic parallelism not possible today.
I will present our recent work in this area. We have extended Haskell’s Par monad with arbitrary
monotonic data structures called LVars. These go beyond single-assignment and include any shared
data structures to which information is added but never removed. Specifically, each LVar is associated
with a lattice from which its states are drawn; writes become join operations; and reads block on a
monotonic threshold functions, preventing observation of the order in which information is added. I
will describe a prototype implementation of this model called LVish, and will describe both its facilities
for task-parallelism with monotonic shared data, and its ability to support other idioms: for example,
parallel in-place update of array locations via a monad-transformer we call VecParT.
8
SBLP 2013
Haskell provides an attractive environment for implementing such approaches, because deterministic
parallelism constructs can be presented as dischargable effects, and used within ordinary (nonIO) purely functional code. The result is that parallel programming mechanisms can be arbitrarily
composed. For example, LVish programs can internally execute GPU code with Accelerate, or use
threaded array parallelism with REPA, or do in-place parallel array computations with a VecParT
transformer, all while modifying and reading monotonic data structures, and all while retaining a full
guarantee of determinism.
Ryan R. Newton grew up in South Florida and received his Ph.D. in computer science from MIT in 2009.
From 2009 through 2011, he was a research scientist at Intel Corporation. In 2011 he joined Indiana
University, where his research focuses on language-based approaches to the programming challenges
posed by future architectures — ranging from embedded sensor nodes to heterogeneous parallel
processors and clusters. His projects employ novel compilation techniques and domain-specific
language designs. With this approach he has made contributions to the areas of: sensor network
programming, stream processing, parallel runtime systems, and automatic program partitioning and
distribution.
Language Design, in Theory and Practice
Tim Harris, Oracle Labs, Cambridge, UK
The end of the “free lunch” of rising CPU clock rates has led to a resurgence of interest in techniques
for parallel programming. Some techniques are well established, coming from fields such as databases
and high-performance computing. Other techniques are more recent, such as programming models
that target GPUs, or that build on the emerging transactional memory systems. To be effective, many
emerging techniques require changes at multiple layers of the stack: a hardware component, support
in the operating system, and changes to the language runtime system in addition to the evolution of
the language itself.
A common theme is that the role of hardware is becoming more significant. This setting creates new
challenges for the programming languages community: how do we reconcile the need for portable
programs and well-defined languages with the ability to use specialized hardware where it is available.
I will talk about my experience trying to tackle instances of these problems, and I will try to identify
some lessons learned. I will focus on three examples. First, transactional memory, and the tensions
that exist between specifying simple language constructs, enabling “transactionalization” of existing
code, and enabling efficient implementations in hardware and software. Second, the message passing
abstractions exposed by the Barrelfish research OS, and the tension between providing well-defined
semantics, while being able to build over diverse forms of communication stack. Finally, I will talk
about my current work on supporting multiple parallel applications together on the same machine, and
how previous work has influenced the design choices there.
Tim Harris has recently joined Oracle Labs in Cambridge, UK. His research interests span multiple
layers of the stack. He is particularly interested in parallel programming, OS / runtime-system
interaction, and opportunities for specialized architecture support for particular workloads. Prior to
Oracle, His recent projects have included language support for asynchronous message passing in the
Barrelfish research OS, and ideas for architecture support for parts of language runtime systems (e.g.,
synchronization and GC). Harris has also worked extensively on transactional memory (TM), most
recently on applying ideas learnt from STM systems to designing an abstraction for low-cost multiword atomic updates for use in building shared-memory data structures. He was on the faculty of the
University of Cambridge, and completed a PhD on providing application programmers with safe control
over low-level features of the JVM (dynamic complication, object placement, thread scheduling).
9
SBLP 2013
Indice / Table of Contents
SHORT PAPER
Tree queries with numerical restrictions: evaluation
and reasoning
12
Ismael Everardo Bárcenas Patiño and José de Jesús Lavalle Martínez
Full Papers (In Portuguese)
Resolução de Bugs de Desempenho via Clonagem de
Funções
17
Guilherme Balena Versiani, Matheus Silva Vilela, Fernando Magno Quintão
Pereira
Prevenção de Ataques de Não-Terminação Baseados
em Estouros de Precisão
32
Raphael Ernani Rodrigues e Fernando Magno Quintão Pereira
Full Papers (Lecture Notes In Computer
Science Vol. 8129)
Exception Handling for Error Reporting in Parsing
Expression Grammars
47
André Murbach Maidl, Fabio Mascarenhas, and Roberto Ierusalimschy
LuaRocks - a Declarative and Extensible Package
Management System for Lua
47
Hisham Muhammad, Fabio Mascarenhas, and Roberto Ierusalimschy
On the Performance of Multidimensional Array
Representations in Programming Languages Based
on Virtual Execution Machines
48
Francisco Heron de Carvalho Junior, Cenez Araújo Rezende, Jefferson
de Carvalho Silva, Francisco José Lins Magalhães, and Renato Caminha
Juaçaba-Neto
Modular Bialgebraic Semantics and Algebraic Laws
Ken Madlener, Sjaak Smetsers, and Marko van Eekelen
10
48
SBLP 2013
A Double Effect Lambda-calculus for Quantum
Computation
48
Juliana Kaizer Vizzotto, Bruno Crestani Calegaro, and Eduardo Kessler Piveta
Boilerplates for Reconfigurable Systems: a
Language and its Semantics
49
Alexandre Madeira, Manuel A. Martins, and Luís S. Barbosa
Contextual Abstraction in a Type System for
Component-Based High Performance Computing
Platforms
49
Francisco Heron de Carvalho Junior, Cenez Araújo Rezende, Jefferson de
Carvalho Silva, and Wagner Guimarães Al-Alam
Towards a Domain-Specific Language for PatternsOriented Parallel Programming
49
Dalvan Griebler, and Luiz Gustavo Fernandes
Multiple Intermediate Structure Deforestation by
Shortcut Fusion
50
Alberto Pardo, João P. Fernandes, and João Saraiva
Zipper-based Attribute Grammars and their
Extensions
Pedro Martins, João Paulo Fernandes, and João Saraiva
11
50
Tree queries with numerical restrictions:
evaluation and reasoning
Everardo Bárcenas1 and Jesús Lavalle2
1
2
Universidad Politécnica de Puebla
Universidad Autónoma de Puebla
Abstract. In query languages design, the efficient evaluation of queries
is one of the major research challenges. Other important issues in this
setting are the testing for emptiness, containment and equivalence of
queries, which are known in general as reasoning problems. In the context of Web systems, we study both subjects, query reasoning and query
evaluation. These problems are traditionally studied separately in different frameworks due to several practical and theoretical challenges. We
propose in this paper a unifying automata-based framework for both,
reasoning and evaluation. In particular, we are interested in the study
of a class of queries, equipped with numerical and schema restrictions in
XPath, which is the standard query language for Web (XML) documents.
1
Introduction
The XPath node-selecting query language over XML documents (tree structures) is one of the core technologies in the development of Web systems. For
instance, the XML transformation language XSLT uses XPath expressions in
the identification of document portions subject to calculations. XPath queries
are also used in several other important XML technologies such as XPointer,
XProc and XForms. Analogously as regular expressions may be used to match
and select text patterns, the intuition behind XPath is that queries serve to
navigate through XML documents and select node subsets (in the document)
matching complex patterns. Queries are like directory paths describing multidirectional tree navigation. For instance the query “child :: a/ancestor :: b” navigates to the children nodes named a, and from there it selects all the ancestors
named b. Numerical restrictions can also be described by specialized constructors: “child :: a[ancestor :: b > descendant :: c]”. This query selects the a children
with more b ancestors than c descendants. However, reasoning on these kind of
queries with full arithmetical constructors is uncomputable [1]. In this paper,
we focus our study on numerical restrictions on children paths w.r.t. a constant,
as for instance the query “ancestor :: a[child :: b > 10]”, which selects the a
ancestors with more than ten b children.
Schema restrictions on XML documents can be described by specialized languages such as DTDs, XML schema and RelaxNG. All these languages are subsumed by regular languages [2], that is, schema restrictions on XML documents
12
are described by regular expressions. However, expressing numerical and schema
restrictions may be extremely expensive. For example, in a regular language with
only “a” and “b”, if we want to restrict “a” to occur more than 2 times, then we
must write: (aaaa? b? )|(aaab? a? )|(aab? aa? )|(ab? aaa? )|(b? aaaa? ). Hardcoding numerical restrictions on regular languages in general produces exponentially larger
expressions than the original problem [3]. This implies exponentially costlier algorithms in the processing of regular schema and numerical restrictions. In order
to avoid the exponential blow-up, we propose in this paper an alternative and
succinct description of numerical and schema restrictions.
There are several recent studies about the representation of numerical restrictions on tree structures [2, 4–6]. However, all those works focus on the study
of reasoning problems only. In [7] there is an extensive study of the Computation Tree Logic (CTL) extended with numerical restrictions. In particular, this
work provides several results regarding the model checking problem. Nevertheless, there is no analysis regarding the satisfiability problem. In contrast with
the works described above, we here propose a novel common framework for both
problems, the satisfiability (reasoning) and the model checking (evaluation) of
expressions on trees with numerical restrictions.
We first introduce in Section 2 a modal tree logic with numerical restrictions
that is used as an assembler language in the description of XPath queries with
numerical and schema constraints. Before concluding in Section 4, in Section 3
we propose a novel automata framework for the logic. This implies an evaluation
and reasoning framework for queries with numerical and schema restrictions.
2
XML logic with numerical restrictions
In this section we introduce an alternation-free two-way graded µ-calculus for
trees, which is a modal logic equipped with constructors for numerical restrictions and multi-directional recursive navigation. We then describe how this logic
can be used as an assembler language for the XML query language XPath with
numerical and schema restrictions.
The syntax of the XML logic with numerical constraints is defined by:
φ := p | x | ¬φ | φ ∨ φ | hmi φ | µx.φ | h↓, ki φ
Formulas are interpreted over tree models as subset nodes. More precisely, propositions p are used as node labels. Negation and disjunction are interpreted as
set complement and union, respectively. Formulas hmi φ holds in nodes s. t.
there is at least one accessible node through m where φ is true. Modalities
m ∈ {↓, →, ↑, ←} are interpreted as the children ↓, right siblings →, parent ↑
and left siblings ←. Formulas µx.φ are interpreted as least fixed-points and they
are used as constructors for finite recursive navigation. Numerical restrictions
h↓, ki φ hold in nodes s.t. there are at least k children nodes where φ holds.
For instance, in a given tree, the following formula holds in nodes with at least
2 children named p1 : h↓, 2i p1 . In Figure 1 is depicted a graphical representation
of a model for this formula. The formula holds in the root of the left subtree, the
only node with two p1 children. Now consider the following example formula:
µx.p2 ∨ h↓i x. This formula holds in nodes with at least 1 descendant (including
13
µx.p2 ∨ h↓i x
p0
P, φ, h↓, 2i p1
p0
p1
p0
p1
p1
p2
Fig. 1. Tree model for: h↓, 2i p1 ; µx.p2 ∨h↓i x; P = child :: p0 ; and φ = p0 ∧h↑i >∧h↓, 2i p1
itself) labeled by p2 . A graphical model for this formula is depicted in Figure 1.
This formula holds in the root, its right children and its rightest descendant.
We also use the following syntactic sugar: φ ∧ ψ ≡ ¬(¬φ ∨ ¬ψ), [m, k] φ ≡
¬ hm, ki ¬φ, and νx.φ ≡ ¬µx.φ. Conjunction follows the traditional De Morgan’s
laws, [↓, k] φ holds in nodes with all but k children nodes where φ is true, and νx.φ
is interpreted as a greatest fixed-point. Interested reader in a formal semantics
of this logic is referred to [2, 8].
2.1
Queries with numerical and schema restrictions
XPath expressions are interpreted over unranked trees (XML documents) as
unary node-selection queries. For instance, the following query selects the children nodes named p in a given tree: “child :: p”. XPath queries can also be composed. Consider for example the following expression: “child :: p1 /descendant ::
p2 ”. This query evaluated from a given node, navigates to the p1 children and
from there it selects the p2 descendants. It is also possible to filter XPath expressions. This is achieved through qualifiers constructors. For example, the
following query selects the p1 children with at least one ancestor named p2 :
“child :: p1 [ancestor :: p2 ]”. More general numerical restrictions can also be
described by means of an specialized constructor. Consider for instance the following query: “descendant :: p1 [child :: p2 > 5]”. This expressions selects the p1
descendants with at least 6 children labeled by p2 . It is important to mention
that only children paths can be numerically restricted. The formal syntax of
XPath queries with numerical restrictions is defined in Figure 2. Note that the
numerical restriction P ≤ k can be writen ¬(P > k).
XPath expression can be concisely expressed in terms of logic formulas (Theorem 1). That is, there is a total function T that maps XPath queries to XML
logic formulas, such that: for every tree, P and T (P ) select the same nodes; and
the size of T (P ) is linear with respect to the size of P . Consider for instance the
following query P : “child :: p0 [child :: p1 > 1]”. This query selects the children
p0 with more than 1 children named p1 . This expression can also be written in
terms of a logic formula φ: “p0 ∧ h↑i > ∧ h↓, 2i p1 ”. h↑i > selects children nodes
only, p0 selects p0 nodes, and h↓, 2i p1 selects nodes with at least 2 children
named p1 . In Figure 1 is depicted a graphical representation of a model for both
P and φ. Notice that the same node is selected in both cases.
There are several domain-specific programming languages used to describe
schema restrictions on XML documents such as XML schema, DTD’s and RelaxNG. All of them are elegantly captured by the Regular Tree Types (RTT) [2],
which can be seen as the tree version of Regular Expressions. For instance the
14
P :=R | /R | P ∪ P | P ∩ P | P \ P
R :=> | a | a :: p | R/R | R[Q]
a :=child | following-sibling | descendant | parent | ancestor
Q :=P | ¬Q | Q ∨ Q | C
C :=child :: p > k | child > k | child :: p[Q] > k | child[Q] > k
Fig. 2. XPath Syntax
expression p[e] denotes the set of trees such that its root is labeled by p and its
children subtrees match with the expression e. In addition RTT expression can
also be composed by numerical restrictions p[e#k ] (# ∈ {>, ≤}) which constrain
the number of children matching a subexpression e with respect to a constant k.
Interested reader in a detailed description of RTT is refered to [9, 2]. Similarly
as XPath queries, RTT expression can also be linearly captured by the logic.
Theorem 1 (Logic embedding [2]). XPath expressions and Regular Tree
Types with numerical constraints are linearly embedded by the XML logic.
3
Two-way weak alternating graded tree automata
In this section we propose a novel automata-based framework for the XML
logic with numerical restrictions. This automata model, named two-way weak
alternating graded tree automata (2WAGTA), is inspired in by the two-way weak
alternating tree automata (2WATA) reported in [9], and the graded alternating
parity tree automata (GAPTA) introduced in [10].
2WAGTA automata run over finite labeled trees. A finite labeled tree is
defined as a pair T = (∆T , lT ), where ∆T is a finite tree and the labeling lT
is left-total mapping from the nodes of ∆T to a set of labels L. A (finite) tree
is a prefix-closed (finite) set of words over the natural numbers N. There is a
well-known bijection between binary and n-ary trees [9]. For technical simplicity
and with out loss of generality, we consider binary trees only.
Before formally define 2WAGTA, let B +(I) be the positive boolean formulae
over the set I, built in directly by applying ∧, ∨, true, false, and the elements in
I. Also consider the set Dk (for 0 ≤ k ∈ N), which is defined by the union of the
sets hki and [k], which in turn are defined by the following sets {h0i, h1i, . . . , hki}
and {[0], [1], . . . , [k]}, respectively. We now define a 2WAGTA automaton with
bound b ∈ N as a tuple (L, S, s0 , δ, α), where: L is a set of labels, S is a set of states,
s0 is the initial state, δ is the transition function S×L 7→ B + ({−1, 0, 1, 2}∪Db×S);
α ⊆ S is the accepting condition discussed below. Consider for instance δ(s1 , p) =
(1, s2 )∨(h5i, s3 ), when the automaton is in state s1 and its reading the node n
labeled with p, it sends either one copy of it in the state s2 to the first successor
of n (n·1) or 5 copies in the state s3 to 5 different children of n.
Because 2WAGTA is a two-way automata, runs can start at any node and not
necessarily in the root. Intuitively, a run follows all transitions that a 2WAGTA
automaton performs on a labeled tree. Formally, a run over a labeled tree T =
(∆T , lT ) from a node n0 ∈ ∆T is a (∆, S)-labeled tree R = (∆R , lR ) satisfying
that ∈ ∆R and lR () = (n0 , s0 ), and if lR (r) = (n, s) and δ(s, lT (n)) = φ, then
there is a (possibly empty) set S 0 = {(c1 , s1 ), . . . , (cm , sm )} ⊆ ({−1.0, 1, 2} ∪
Db ) × S, such that S 0 satisfies φ and for all i = 1, . . . , m the following hold for
15
each ci : if ci ∈ {−1, 0, 1, 2}, then r · i ∈ ∆R , n · ci ∈ ∆T and lR (r · i) = (n · ci , si );
if ci = hki, then there are distinct i1 , . . . , ii+1 ∈ N? , such that r · j 0 ∈ ∆R and
lR (r · j 0 ) = (n · ij , si ); and if ci = [k], then there are distinct i1 , . . . , ib−k ∈ N? , such
that for all j = 1, . . . , b−k there is a j 0∈N? such that r·j 0∈∆R and lR (r·j 0 ) = (n·ij , si ).
We now define the
S weak acceptance condition α ⊆ S. There is a partition of
S disjoints sets Si ( Si = S), such that either Si ⊆ α, in which case Si is an
accepting set, or α ∩ Si = ∅, in which case Si is a rejecting set. In addition, there
is a partial order ≺ s.t. for s ∈ Si and s0 ∈ Sj (i 6= j), if s0 occurs in δ(s, a),
for some a ∈ L, then Sj ≺ Si . A run is accepting if all its infinite paths are
accepting. A node n is selected by a 2WAGTA A from a labeled tree T if there
exists an accepting run of A over T from n.
Theorem 2. Given a XML logic formula φ, there is a 2WAGTA A, such that
for any tree, φ selects exactly the same nodes that A.
Then from Theorems 1 and 2, 2WAGTA serves as a framework for the evaluation
and reasoning of XPath queries with numerical and schema restrictions.
4
Conclusions
We have proposed a novel automata framework for describing numerical restrictions on tree structures. It has been carefully designed for the efficient evaluation
and reasoning of XPath queries with numerical and schema restrictions. We are
currently proving linear time complexity for query and evaluation and exponential time for query reasoning. The implementation of the automata model is also
under current work.
References
1. ten Cate, B., Marx, M.: Axiomatizing the logical core of XPath 2.0. Theory
Comput. Syst. 44(4) (2009)
2. Bárcenas, E., Genevès, P., Layaı̈da, N., Schmitt, A.: Query reasoning on trees with
types, interleaving, and counting. In Walsh, T., ed.: IJCAI, IJCAI/AAAI (2011)
3. Gelade, W.: Succinctness of regular expressions with interleaving, intersection and
counting. Theor. Comput. Sci. 411(31-33) (2010)
4. Seidl, H., Schwentick, T., Muscholl, A.: Counting in trees. In: Logic and Automata.
(2008)
5. Demri, S., Lugiez, D.: Complexity of modal logics with Presburger constraints. J.
Applied Logic 8(3) (2010)
6. Bianco, A., Mogavero, F., Murano, A.: Graded computation tree logic. ACM
Trans. Comput. Log. 13(3) (2012)
7. Laroussinie, F., Meyer, A., Petonnet, E.: Counting CTL. Logical Methods in
Computer Science 9(1) (2012)
8. Bonatti, P.A., Lutz, C., Murano, A., Vardi, M.Y.: The complexity of enriched
mu-calculi. Logical Methods in Computer Science 4(3) (2008)
9. Calvanese, D., Giacomo, G.D., Lenzerini, M., Vardi, M.Y.: Node selection query
languages for trees. In Fox, M., Poole, D., eds.: AAAI, AAAI Press (2010)
10. Kupferman, O., Sattler, U., Vardi, M.Y.: The complexity of the graded µ-calculus.
In Voronkov, A., ed.: CADE. Volume 2392 of Lecture Notes in Computer Science.,
Springer (2002)
16
Resolução de Bugs de Desempenho via
Clonagem de Funções
Guilherme Balena Versiani, Matheus Silva Vilela,
Fernando Magno Quintão Pereira
Departamento de Ciência da Computação – UFMG – Brasil
{guibv,matheusv}@dcc.ufmg.br
Resumo Desenvolvedores normalmente reusam módulos de software
para obter uma funcionalidade especı́fica. Contudo, muitas vezes, esses componentes, usados como caixas-pretas, realizam mais ações que
o esperado. A esse fenômeno dá-se o nome de bug de desempenho. A
detecção desse tipo de problema é difı́cil, pois sua ocorrência depende
do contexto em que o módulo é reutilizado. Em alguns desses contextos, todas as computações feitas pelo módulo são necessárias, em outros
não. Neste artigo, propomos um mecanismo para detectar e sanar automaticamente dois tipos de bugs de desempenho: valor de retorno não
usado e não distinção de apontadores. Uma vez encontrados esses bugs,
nós realizamos a clonagem automática das funções problemáticas, substituindo as chamadas das funções originais por chamadas de clones sempre
que possı́vel. Implementamos as otimizações propostas em LLVM 3.2 e
observamos que ambos os bugs de desempenho são muito comuns. Aproximadamente 16% das funções encontradas em SPEC CPU 2006 podem
beneficiar-se da eliminação de valores de retorno, enquanto 33% delas podem beneficiar-se da distinção de apontadores. Em alguns benchmarks,
nossas técnicas levaram a ganhos de até 31% em relação a LLVM -O2.
Resumo The ability to reuse software is one of the fundamental skills
of the contemporary program developer. However, this skill must be used
with discipline, or programmers may insert into their systems modules
that do more work than what they need. This phenomenon is called a
performance bug. Detecting this problem is difficult, because it depends
on the context in which components are reused. In some contexts all
the computations performed by the module may be necessary, in others
they may not. In this paper, we use function cloning to give the compiler the freedom to solve two types of performance bugs: unused return
values and pointer disambiguation. We have designed a compiler pass
that (i) recognizes problematic functions, (ii) clones them, (iii) eliminates the buggy feature from the clone and (iv) replaces every call of the
original function by its new version, whenever the calling context allows
it. We have implemented our technique in LLVM, and have found that
both these performance bugs are very common, even in highly optimized
code. We found that 16% of the functions in SPEC CPU 2006 produce
unused return values, and 33% of them could benefit from pointer disambiguation. Our techniques have been able to speedup well-known public
benchmarks by up to 31% on top of LLVM -O2.
17
1
Introdução
O reúso de software foi uma das principais forças que impulsionaram o vertiginoso crescimento da informática nas últimas décadas [13]. Prova disso é a
importância que a academia e a indústria atribuem a práticas tais como a programação por contrato, o encapsulamento de informação e o desenvolvimento de
grandes bibliotecas de componentes. De fato, é justo dizer que o surgimento e popularização das linguagens orientadas a objetos mudou a forma que a indústria
de software vê a atividade de programação. Nos anos dourados da programação
estruturada, antes do advento dos objetos, um programador era valorizado por
sua capacidade de desenvolver algoritmos de forma clara e eficiente [5]. Hoje,
contudo, cinquenta anos após a revolução iniciada por Simula e continuada por
Smaltalk, C++ e Java, muito do valor de um profissional da informática reside
em sua capacidade de reusar software já pronto [9]. Entretanto, ainda que poderosa, a prática do reúso de componentes requer disciplina, ou pode levar a
problemas tais como bugs de desempenho.
De acordo com Jin et al. [10], um bug de desempenho caracteriza-se por
comportamento que compromete a eficiência de um programa de forma desnecessária, sem causar erros observáveis em sua saı́da. Jin et al. argumentam que
a principal razão por trás desse tipo de problema é o reúso indiscriminado de
software. Muitas vezes, programadores reutilizam componentes a fim de obter
uma funcionalidade especı́fica, sem importar-se com o fato desses componentes realizarem diversas outras ações não relacionadas àquela funcionalidade. À
essa causa, juntamos outra: a evolução natural das linguagens de programação.
Exemplo dessa fonte de bugs de desempenho é o modificador restrict, introduzido no padrão C99. Esse modificador permite que o desenvolvedor de software
indique ao compilador C que dois ou mais ponteiros, passados como parâmetro
de função, não se sobrepõem. De posse dessa informação, o compilador é capaz
de realizar otimizações mais agressivas sobre o programa alvo. Entretanto, tendo
sido esse modificador criado em fins da década de 90, os programas então existentes dele não puderam se beneficiar. Além disso, o hábito, aliado à ignorância,
faz com que essa palavra chave não seja popular entre desenvolvedores C.
Bugs de desempenho normalmente não podem ser removidos por otimizações
tradicionais de código. A limitação dos compiladores, nesse caso, deve-se ao
contexto. Os resultados produzidos por um componente de software podem ser
úteis em determinados contextos e irrelevantes em outros. A integração de procedimentos, ou inlining de funções, é uma forma que compiladores possuem de
mitigar tais problemas. Entretanto, a integração de procedimentos pode levar
a um crescimento exponencial do programa transformado. Além disso, funções
recursivas não podem ser integradas [12, pg.458]. Outro problema que compiladores enfrentam para eliminar bugs de desempenho está relacionado à escala
em que essas transformações deveriam ser feitas. A resolução desse tipo de bug
demanda a análise de um programa inteiro, via algoritmos que muitas vezes são
computacionalmente caros. Nesse artigo, nós propomos uma solução simples e
completamente automática para resolver alguns bugs de desempenho especı́ficos.
18
O objetivo deste trabalho é implementar e testar uma técnica, baseada na
clonagem de funções, que elimina alguns bugs de desempenho. Tal tecnologia
é um segundo caminho que compiladores podem usar, além da integração de
procedimentos, para obter sensibilidade a contexto. Em essência, procuraremos
separar os pontos de chamada de funções em duas classes de equivalência: a
primeira, denominada promissora, contém as chamadas que podem se beneficiar
de uma otimização especı́fica, enquanto a segunda, denominada inócua, contém
as chamadas para as quais tal otimização não se aplique. Assim, para cada uma
de nossas otimizações propostas, teremos dois clones de cada função otimizável.
Um desses clones, que chamaremos de modificado, terá seu código melhorado
segundo os critérios da otimização especı́fica. As chamadas promissoras serão
substituı́das por chamadas da função modificada, enquanto as chamadas inócuas
continuarão invocando a função original. Limitaremos assim, em duas replicações
somente, a expansão de código devido à existência de contextos diferentes.
Neste artigo, nós estudaremos duas otimizações especı́ficas: eliminação de
valores de retorno não usados e distinção de apontadores. A primeira dessas
otimizações será aplicada nos contextos em que o valor de retorno da função
invocada não é usado pelo código invocador. O clone modificado não conterá
qualquer computação relacionada exclusivamente à produção do valor de retorno. A segunda otimização será aplicada a funções que recebem ponteiros como
parâmetros. Muitas vezes, a possibilidade de que tais ponteiros sejam sinônimos,
isto é, que dereferenciem a mesma região de memória, restringe as otimizações
que o compilador consegue aplicar sobre a função. Nos contextos promissores,
em que nossa análise de apontadores indique a inexistência de sinônimos, nós
invocaremos uma função modificada. Esse clone é criado com a informação de
que seus parâmetros apontam para regiões de memória distintas. Estando o compilador liberto da tarefa de considerar que ponteiros podem ser sinônimos, suas
análises podem ser muito mais precisas e suas otimizações muito mais extensivas.
Implementamos as técnicas descritas neste trabalho no compilador
LLVM [15], e nosso código está publicamente disponı́vel para escrutı́nio 1 . Os
resultados obtidos até agora mostram-se promissores. A eliminação de valores de
retorno pôde ser aplicada a 16% das funções disponı́veis em SPEC CPU 2006.
O alcance da distinção de apontadores é ainda mais impressionante: cerca de
um terço de todas as funções encontradas em SPEC CPU 2006 recebe dois ou
mais ponteiros como parâmetro, sendo que 99% das chamadas dessas funções
são promissoras, podendo, assim, ser substituı́das por clones. Nossos ganhos de
desempenho foram pequenos: os programas melhorados ficaram, em média, menos que 2% mais rápidos. Consideramos aqui que ambos os programas, original
e transformado, são compilados com LLVM -O2. Especulamos que os ganhos pequenos devem-se ao fato de termos realizado essas otimizações sobre SPEC CPU
2006, uma coleção de programas já muito otimizados. Para testar tal hipótese,
aplicamos nossas técnicas sobre aplicações de código aberto, obtendo resultados
notáveis. Por exemplo, a distinção de apontadores, quando aplicada à alguns
benchmarks da companhia Adobe, levou a ganhos de desempenho de até 31,2%.
1
https://code.google.com/p/clone-based-opts
19
1
2
3
4
5
6
7
8
9
int divMod(int a, int b, int* m) {
int quot = 0;
while (a > b) {
a -= b;
quot++;
}
*m = a;
return quot;
}
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
int main(int argc, char** argv) {
int modulus;
int quotient;
switch(argc) {
case 1:
quotient = divMod(argv[0][0], argv[0][1], &modulus);
printf("quotient = %d, modulus = %d\n", quotient, modulus);
break;
case 2:
divMod(argv[0][0], argv[1][0], &modulus);
printf("modulus = %d\n", modulus);
break;
case 3:
divMod(argv[1][0], argv[2][0], &modulus);
break;
}
}
Figura 1. Exemplo que se beneficia de eliminação de valores de retorno não usados
via clonagem de funções.
2
As Otimizações Propostas
Conforme discutimos na seção anterior, neste artigo experimentamos duas otimizações diferentes baseadas na clonagem de funções: a eliminação de valores
de retorno não usados e a distinção de apontadores. Nesta seção, ilustraremos
cada uma dessas transformações de código via exemplos. Apesar de tais transformações serem aplicadas na representação intermediária da LLVM, usaremos
exemplos em C para facilitar o entendimento.
Eliminação de Valores de Retorno não Usados. A fim de descrever a
primeira dessas otimizações, usaremos o exemplo da figura 1. A função divMod
recebe dois parâmetros, a e b, retornando o quociente da divisão de a por b. Além
disso, a função recebe um terceiro argumento, m, usado para simular a passagem
de parâmetro por resultado. Esse argumento recebe o resto da divisão inteira.
Em nosso exemplo, a função divMod é usada em três contextos diferentes, nas
linhas 16, 20 e 24 do procedimento main. Em dois desses contextos, a saber, nas
20
linhas 20 e 24, o valor de retorno produzido pela função não é usado. Por outro
lado, uma vez que esse valor é necessário no primeiro contexto, sua computação
não pode ser simplesmente removida do corpo de divMod.
A figura 2 conclui nosso exemplo inicial, mostrando o resultado produzido
por nossa primeira otimização: a eliminação de valores de retorno não utilizados. Nesse caso, nós fomos capazes de clonar a função divMod, produzindo a nova
função divMod noret, que não possui qualquer computação usada para determinar o valor final da variável quot. Nesse exemplo, fomos capazes de substituir
a chamada original de divMod em dois contextos diferentes, nas linhas 10 e 14
da função principal. O reconhecimento de contextos promissores nesse caso é
simples: uma chamada r = f (. . .) pode ser substituı́da se o nome que ela define
como retorno – r – é código morto. A detecção de código morto dá-se segundo
uma análise clássica de código que omitimos por brevidade [2, p.417]. Conforme
mostraremos na seção 3, mesmo programas muito otimizados apresentam boas
oportunidades para a eliminação de valores de retorno não utilizados. Tais oportunidades partem, conforme mencionamos anteriormente, dos chamados bugs de
desempenho. A existência de valores de retorno não usados é mencionada por
Jin et al. como uma consequência da má prática de programação [10].
Distinção de Apontadores. Apontadores são frequentemente encontrados na
assinatura de funções tipicamente vistas em aplicações escritas em C ou C++.
Em particular, ponteiros são utilizados para simular a passagem de parâmetros
por referência ou por resultado em C. O apontador m*, na figura 1, ilustra
essa última prática. Apontadores comprometem sobremaneira o alcance das otimizações que um compilador pode aplicar sobre um programa. Nós usaremos o
programa visto na figura 3, para exemplificar essa situação. Esse exemplo foi inicialmente descrito por Chabbi e Crummey [3] em um trabalho recente 2 , também
como um exemplo de bug de desempenho.
O programa visto na figura 3 pode escrever duas vezes sobre várias posições
do vetor r. Tal redundância é necessária, pois os vetores b e r podem ser
sinônimos. Caso tal sobreposição não fosse possı́vel, então o compilador poderia
transformar a função copy em copy noAlias, cujo código é visto na figura 4.
Nessa nova versão de copy o vetor r foi marcado com o modificador de tipo
restrict. Esse modificador é um recurso que o desenvolvedor possui para informar ao compilador que um ponteiro não possui sinônimos no escopo da função
em que é parâmetro formal. De posse dessa informação, o compilador pode substituir as duas escritas sobre o vetor r por duas escritas em um temporário, conforme visto nas linhas 4 e 6 da figura 4. Esse temporário será escrito em memória
uma única vez, na linha 8 daquela figura. Note que caso os vetores r e b fossem
sinônimos, então a escrita na linha 4 da figura 3 seria estritamente necessária,
pois ela poderia influir no resultado do teste realizado na linha 5. Embora essa
otimização seja muito localizada, seus resultados são formidáveis. Experimentos
que realizamos em uma máquina Intel Core 2 Duo de 2.27GHz, usando vetores
de 100.000 posições, revelam que a implementação de copy noAlias é quase três
vezes mais rápida que a implementação de copy.
2
Nós adaptamos o exemplo mostrado nas listagens três e quatro de [3].
21
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
int divMod(int a, int b, int* m) {
int quot = 0;
while (a > b) {
void divMod_noret(int a, int b, int* m) {
a -= b;
while (a > b) {
quot++;
a -= b;
}
}
*m = a;
*m = a;
return quot;
}
}
int modulus;
int quotient;
switch(argc) {
case 1:
quotient = divMod(argv[0][0], argv[0][1], &modulus);
printf("quotient = %d, modulus = %d\n", quotient, modulus);
break;
case 2:
divMod_noret(argv[0][0], argv[1][0], &modulus);
break;
case 3:
divMod_noret(argv[1][0], argv[2][0], &modulus);
break;
}
}
Figura 2. Programa obtido a partir da eliminação de valores de retorno não usados
via clonagem de funções.
A função copy noAlias, um clone de copy, pode ser usada em todos os contextos em que os valores passados via os argumentos b and r não são sinônimos.
Em nosso exemplo, essa condição é verdadeira para a chamada de copy na linha
17 da figura 3. O desafio de reconhecer contextos promissores para distinção de
apontadores é substancialmente mais difı́cil que para a eliminação de retornos
não usados. A fim de determinar se dois ponteiros são sinônimos ou não, implementamos a análise de apontadores de Andersen [1]. Além disso, aumentamos
a nossa implementação com a detecção de ciclos tardia proposta por Hardekopf
e Lin [8], para permitir que a análise de apontadores terminasse rapidamente,
mesmo para programas tão grandes quanto os disponı́veis em SPEC CPU 2006.
Nossa implementação não é sensı́vel ao fluxo de execução do programa. Existem abordagens mais precisas para a análise de apontadores, porém elas ainda
não são tecnologicamente práticas, dado o tamanho dos programas que analisamos. Ainda assim, conforme mostraremos na seção 3, nossa implementação é
capaz de distinguir os ponteiros usados em quase todas as chamadas de funções
disponı́veis nos programas de teste que usamos.
22
1
2
3
4
5
6
7
8
9
void copy(char* a, char* b, char* r, int N) {
int i;
for (i = 0; i < N; i++) {
r[i] = a[i];
if (!b[i]) {
r[i] = b[i];
}
}
}
10
11
12
13
14
15
16
17
18
19
20
char* buf = (char*) malloc(SIZE*sizeof(char));
if (argc < 2) {
strcpy(buf, argv[0]);
copy(argv[0], buf, buf, SIZE);
} else {
copy(argv[0], argv[1], buf, SIZE);
}
print(buf, SIZE);
}
Figura 3. Exemplo em que a possı́vel sobreposição de ponteiros pode impedir otimizações de código.
1
2
void copy_noAlias(char* a, char* b, restricted char* r, int N) {
int i;
3
for (i = 0; i < N; i++) {
int tmp = a[i];
4
if (!b[i]) {
tmp = b[i];
5
6
}
r[i] = tmp;
7
8
}
9
10
}
Figura 4. Versão otimizada de copy, a função vista na figura 3.
Nı́vel de Sensibilidade a Contexto. As análises de código sensı́veis a contexto de chamada de funções são notoriamente caras. Muitas vezes, esse preço
leva à compromissos, como a adoção de estruturas de dado que consomem grande
23
quantidade de memória [19], ou a uma perda aceitável de precisão [16]. As otimizações que propomos no presente texto não incorrem nesses custos. Efetivamente, nossas otimizações são disparadas por uma análise sensı́vel ao contexto
do tipo 0-CFA [17]. Em outras palavras, nosso contexto é formado por somente
um nı́vel de chamada de função. Somos capazes de distinguir uma chamada de
função de outra, mas não somos capazes de distinguir invocações em sequências
de duas ou mais chamadas aninhadas de função. Embora não tenhamos implementado a distinção de nı́veis mais profundos de contextos de invocação, especulamos, partindo dos resultados obtidos por Lhotak et al. [16], que nı́veis extra
aumentariam muito pouco o alcance de nossas otimizações.
3
Resultados Experimentais
Essa seção descreve uma série de experimentos que realizamos para validar tanto
a eliminação de valores de retorno não usados, quanto a distinção de apontadores.
As otimizações foram testada em uma máquina com 12 núcleos de processamento
Intel Xeon CPU E5-2665, com clock de 2.40GHz, 132 GB de RAM, executando
o sistema operacional Ubuntu 12.04. Nossas otimizações foram implementadas
sobre LLVM 3.3. Os testes que mostramos nesta seção foram executados sobre
SPEC CPU 2006.
Implementação das Otimizações A figura 5 descreve a sequência de transformações pela qual passa um programa que otimizamos. A duas otimizações
que descrevemos neste artigo são completamente independentes, podendo ser
aplicadas juntas, ou em separado. Cada uma dessas otimizações contém três
etapas:
1. Identificação: são reconhecidas as funções que, devido à algum contexto de
chamada, podem se beneficiar da clonagem.
2. Clonagem: é criado um clone para cada função marcada na etapa anterior.
3. Substituição: chamadas promissoras são substituı́das por chamadas da
função clonada.
Findas essas três etapas, aplicamos sobre o programa transformado as otimizações disponı́veis em LLVM -O2. São essas otimizações que irão, efetivamente,
polir o código da função clonada. Por exemplo, ao eliminarmos o valor de retorno de uma função, nós não removemos as computações necessárias ao seu
cálculo. Deixamos tal tarefa a cargo de LLVM -O2. Durante nossos experimentos,
nós omitimos a integração de procedimentos (inlining) desse conjunto de otimizações. Fizê-mo-lo porque a integração de procedimentos torna difı́cil medir
os ganhos obtidos por nossa otimização, uma vez que muitas das chamadas das
funções originais e clonadas são removidas do programa. Finalmente, antes de
produzirmos um executável, nós eliminamos os chamados clones órfãos. Se todas
as chamadas de uma função clonada forem promissoras, então a versão original
daquela função deixará de ser alcançável. Tais funções – denominadas órfãs –
são eliminadas nessa etapa final.
24
Clonagem de funções cujo valor de retorno
não é utilizado depois da chamada
Identificação
Clonagem
Substituição
Programa
Original
LLVM -O2
exceto inline
Eliminação de
clones órfãos
Clonagem de funções cujos parâmetros
não podem apontar para a mesma memória.
Identificação
Clonagem
Substituição
Figura 5. Sequência de transformações que usamos para aplicar a clonagem de funções.
Alcance das otimizações propostas. A figura 6 mostra o alcance da eliminação de valor de retorno não utilizado. Nós estamos separando o conjunto
de chamadas de funções nos programas alvo em três classes de equivalência.
A primeira classe contém as chamadas de funções que não foram clonadas. No
exemplo da figura 1 temos três chamadas indiferentes: tratam-se das invocações
de printf nas linhas 17, 21 e 25. A segunda classe agrupa as chamadas que puderam ser substituı́das por invocações de clones. Ainda no exemplo da figura 1,
temos duas chamadas promissoras de divMod, nas linhas 20 e 24. Finalmente,
a classe inócua contém as chamadas de funções clonadas que não foram substituı́das por clones, uma vez que seu contexto torna essa substituição impossı́vel.
Em nosso exemplo, temos somente uma chamada inócua: a invocação de divMod
na linha 16.
A figura 7 mostra os mesmos dados que a figura 6, porém para a nossa
segunda otimização: a distinção de apontadores. Observa-se, via a comparação
das figuras 6 e 7, que a distinção de apontadores é visivelmente mais aplicável
que a eliminação de valores de retorno não usados. Em particular, quase todas
as chamadas de funções clonadas mostraram-se promissoras. Justifica-se esse
alcance segundo uma observação já conhecida desde longa data [14]: raramente
programadores passam, via argumentos diferentes de uma mesma invocação de
função, apontadores para estruturas de dados que se sobrepõem.
Expansão de código. A figura 8 mostra a expansão de código devido à clonagem de funções. O tamanho dos programas depois da clonagem é dado pelo
número total de bytecodes LLVM que ele apresenta após a eliminação de clones órfãos. Em outras palavras, esse é o tamanho do programa, em número de
instruções, após o último estágio da sequência mostrada na figura 5. Usamos
a chamada integração simples, que aninha funções segundo uma heurı́stica bastante elaborada. Essa heurı́stica tende a integrar funções pequenas – com poucas
instruções – e funções não recursivas que são utilizadas somente uma vez, por
exemplo. Após a clonagem, ou a integração de procedimentos, o programa é
compilado com a diretiva -O2, para que otimizações dependentes de contexto
possam ser aplicadas. Essa diretiva, por padrão, realiza a integração simples.
Naturalmente, a integração foi removida ao efetuarmos a clonagem. Conforme
25
Benchmark
Funções Clones Órfãs
Indiferentes Promissoras
Inócuas
400.perlbench
1863
149
10
6535 (43%) 1718 (11%) 6980 (46%)
401.bzip2
99
10
0
362 (81%)
21 (5%)
63 (14%)
403.gcc
4450
234
15
16378 (32%)
2766 (5%) 32546 (63%)
429.mcf
25
6
0
61 (76%)
8 (10%)
11 (14%)
445.gobmk
2679
45
1
4102 (40%) 1209 (12%) 4898 (48%)
456.hmmer
536
22
1
2923 (69%)
75 (2%) 1211 (29%)
458.sjeng
132
0
0
1086 (82%)
0 (0%)
238 (18%)
462.libquantum
115
8
0
389 (74%)
38 (7%)
101 (19%)
464.h264ref
589
40
6
2870 (76%)
219 (6%)
694 (18%)
470.lbm
17
0
0
67 (100%)
0 (0%)
0 (0%)
471.omnetpp
2836
116
28 13126 (100%)
867 (7%) 6031 (46%)
473.astar
149
7
0
381 (60%)
8 (1%)
251 (39%)
483.xalancbmk
28877
1599 1029
60723 (83%)
3198 (4%) 30726 (42%)
433.milc
235
5
0
1406 (80%)
127 (7%)
223 (13%)
436.cactusADM
1390
217
23
3138 (41%) 2072 (27%) 2446 (32%)
444.namd
154
5
4
1367 (86%)
15 (1%)
236 (15%)
447.dealII
19644
1374
797
44218 (59%)
3683 (5%) 39799 (53%)
450.soplex
1639
82
39
4154 (47%)
358 (4%) 4852 (55%)
453.povray
2028
100
11
9773 (63%)
1383 (9%) 4394 (28%)
454.calculix
1383
60
3
18021 (88%)
347 (2%) 2214 (11%)
482.sphinx3
369
22
5
2058 (74%)
27 (1%)
709 (25%)
Figura 6. Alcance da eliminação de valores de retorno não usados. Funções: número total de funções no benchmark original, antes da aplicação de clonagem. Clones: número
de funções clonadas. Órfãs: número de funções originais que passaram a não ser mais
usadas, devido a substituição de todas as suas chamadas por clones. Indiferentes:
quantidade de chamadas de funções não clonadas. Promissoras: número de chamadas de funções substituı́das por invocações de clones. Inócuas: número de chamadas
de função que tiveram clones gerados, mas que não foram substituı́das.
podemos ver pela figura, a eliminação de valores de retorno gera programas menores que a integração de procedimentos em 15 (de 19) benchmarks. A distinção
de apontadores o faz em 15 (de 21) benchmarks. A integração é mais econômica
em alguns casos porque ela foi implementada de forma tı́mida. Ao fato de que
poucas funções são integradas, soma-se o fato de que as que o foram são removidas do código final. A clonagem, por outro lado, é aplicada extensivamente, e
gera a duplicação de várias funções. Ainda assim, a clonagem é mais econômica
na maior parte dos casos.
Variação no tempo de execução. A figura 9 mostra a variação no tempo
de execução dos programas devido a nossas otimizações. Os tempos de execução
foram obtidos com um intervalo de confiança de 95.0%, tendo sido coletadas cinco
amostras por programa examinado. Estamos comparando os programas obtidos
após a aplicação do último estágio mostrado na figura 5, com os programas
obtidos via a aplicação de todas as otimizações presentes em LLVM -O2. A média
geométrica de ganho, devido a distinção de apontadores, foi de 1.03%. Nosso
26
Benchmark
400.perlbench
401.bzip2
403.gcc
429.mcf
445.gobmk
456.hmmer
458.sjeng
462.libquantum
464.h264ref
470.lbm
471.omnetpp
473.astar
483.xalancbmk
433.milc
436.cactusADM
444.namd
447.dealII
450.soplex
453.povray
454.calculix
482.sphinx3
Funções
1863
99
4450
25
2679
536
132
115
589
17
2836
149
28877
235
1391
154
19644
1639
2028
1383
369
Clones
349
19
1789
7
208
162
13
4
98
8
562
34
10733
77
292
39
7908
338
647
590
129
Órfãs
340
19
1767
7
206
162
12
4
98
8
560
34
10716
72
289
39
7896
335
614
586
129
Indifer.
7454 (67%)
213 (87%)
28840 (64%)
22 (76%)
6958 (83%)
1527 (73%)
560 (92%)
351 (98%)
1170 (67%)
17 (57%)
8728 (73%)
417 (86%)
44357 (61%)
488 (58%)
2320 (50%)
346 (69%)
50656 (73%)
6500 (84%)
4793 (46%)
2993 (52%)
1284 (63%)
Promissoras
3604 (33%)
32 (13%)
16078 (36%)
7 (24%)
1379 (17%)
555 (27%)
49 (8 %)
9 (3 %)
585 (33%)
13 (43%)
3294 (27%)
70 (14%)
28086 (39%)
352 (42%)
2281 (50%)
152 (31%)
18707 (27%)
1201 (16%)
5577 (54%)
2783 (48%)
765 (37%)
Inócuas
15 (0%)
0 (0%)
65 (0%)
0 (0%)
5 (0%)
0 (0%)
1 (0%)
0 (0%)
0 (0%)
0 (0%)
2 (0%)
0 (0%)
22 (0%)
47 (6%)
3 (0%)
0 (0%)
22 (0%)
4 (0%)
213 (2%)
37 (1%)
0 (0%)
Figura 7. Alcance da distinção de apontadores.
melhor resultado, nesse caso, foi 7.14% obtido sobre 483.xalancbmk, e nosso pior
número foi -2,03% em 433.milc. Nós não pudemos obter resultados conclusivos
com a eliminação de valores de retorno: a maior parte de nossos resultados
ficaram dentro de uma margem de variação de -1.0% e +1.0%. As exceções
do lado positivo foram 450.soplex e 453.povray, com ganhos de velocidade
de 1.28% e 3.64%. Registramos perdas em 429.mcf e 433.milc, que ficaram
1.14% e 1.67% mais lentos. Uma inspeção do código produzido não revelou causa
aparente para tais perdas.
Especulamos que esses resultados tı́midos devem-se ao fato de estarmos testando nossas otimizações sobre os programas disponı́veis em SPEC CPU 2006.
Esses programas foram escritos por profissionais expertos, e vêm sendo gradualmente melhorados desde longa data. Em outros benchmarks menos otimizados pudemos registrar ganhos maiores. Por exemplo, a companhia Adobe
possui uma coleção de seis programas usados em testes de desempenho publicamente disponı́veis em http://stlab.adobe.com/performance/. Ao aplicarmos a distinção de apontadores sobre esses programas, pudemos obter um
ganho de 31.20% em um deles, loop unroll.c. Registramos também ganhos
em outros três: simple types loop.c (3.81%), functionobjects.c (3.86%) e
simple types const.c (4.15%).
27
9.000.000 8.000.000 7.000.000 6.000.000 5.000.000 4.000.000 3.000.000 2.000.000 1.000.000 lix
de
al
II M
lcu
AD
ca
gc
c
go bm
h2 k 64
re
hm f m
er
lb
lib
qu m an
tu
m
m
cf
m
ilc
na
m
om d ne
pe tpp
rlb en
ch
po vr
ay
sje
ng
so pl
e
sp x hi
xa nx3
la
nc bm
k ca
ct
us
ta
r
as
bz
ip
2 0 Ret-‐Elim -‐O2 Pointer-‐Dis -‐O2 Inline -‐O2 Figura 8. Expansão de código devido à clonagem de funções. Tamanho é medido em
número de bytecodes LLVM. Inline: integração simples de procedimentos. Ret-Elim
e Pointer-Dis: nossas otimizações.
8 6 4 2 0 lb
m
as
ta
r so
pl
ex
bz
ip
2 h2
64
re
f de
al
II go
lib bm
k qu
an
tu
m
po vr
ay
sp
hi
nx
3 m
cf
pe
rlb en
om ch ne
tp
p na
m
d
hm m
er
s
ca jen
g ct
us
AD
M
gc
c
ca lcu
lix
m
ilc
xa
la
nc
bm
k ‐2 Figura 9. Variação no tempo de execução dos benchmarks devido à distinção de
apontadores. Barras representam percentual de ganhos entre LLVM -O2 mais nossa otimização, e LLVM -O2 sem ela. Quanto maior a barra, maior o ganho conseguido por
nossa otimização.
Decidimos averiguar o porquê de a eliminação de retornos não surtir maior
efeito nos programas encontrados em SPEC CPU 2006. Com tal intuito, observamos que muitas funções clonadas têm apenas uma instrução de retorno, por
exemplo, “ret 1”, substituı́da por “ret void”. Em outras palavras, o valor de
retorno simplesmente indica se a função executou corretamente, como no caso
da ubı́qua implementação de printf, onde valores positivos indicam sucesso e
28
0.25 0.2 0.15 0.1 0.05 ReducGon = 3% ReducGon = 2% om
ne
tp
p na
m
d m
ilc
go
bm
k m
er
gc
c
hm
ca
ct
us
m
cf
AD
M
bz
ip
2 pe
rlb
en
ch
de
a
lib
lII
qu
an
tu
m
h2
64
re
f sp
hi
nx
xa
3 la
nc
bm
k so
pl
ex
po
vr
ay
as
ta
r ca
lcu
lix
0 ReducGon = 1% Figura 10. Taxa de redução de código das funções otimizadas com a eliminação de
valores de retorno não usados.
valores negativos indicam erro. Para verificar quantas funções são efetivamente
otimizadas, nós as separamos em grupos, de acordo com a taxa de redução de
código. Esse resultado pode ser visto na figura 10. Nessa figura, a barra de 3%,
por exemplo, indica a percentagem de funções que tiveram pelo menos três por
cento de seu código reduzido. Conforme podemos ver pela figura, poucas funções
enquadram-se nessa categoria.
4
Trabalhos Relacionados
A ideia de clonar funções para que otimizações dependentes de contexto possam
ser aplicadas sobre o seu código não é nova. Em seu recente livro texto, Grune
et al., por exemplo, descrevem a clonagem como uma forma de aumentar o alcance da propagação de constantes [6, pg.325]. Os algoritmos mencionados por
Grune et al. parecem ter sido inicialmente propostos por Mary Hall em sua dissertação de doutorado [7, Cp.5]. Nesse caso, a clonagem é comumente chamada
especialização de código. A técnica de Hall pode ser descrita como especialização
estática. A contraparte dinâmica existe também. Costa et al. mostraram como
clonar funções no contexto da compilação just-in-time para realizar a propagação
de constantes em código especializado [4]. Ainda assim, é surpreendentemente
difı́cil encontrar, na literatura de linguagens de programação, discussões sobre
a clonagem de funções para a implementação de otimizações dependentes de
contexto. Compiladores industriais, tais como icc e LLVM não utilizam a clonagem. O compilador gcc pode realizar a clonagem de uma função que possui somente um sı́tio de invocação, e que recebe constantes como parâmetros. Também
open64 é capaz de clonar funções, mas assim como gcc, somente para facilitar
a propagação de constantes.
Bugs de desempenho vêm sendo estudados com afinco pela comunidade cientı́fica. Esse interesse é recente, e tem levado a avanços consideráveis no que
tange a diagnose e o tratamento desse tipo de problema. Jovic et al. [11], por
exemplo, demonstraram que muitos bugs de desempenho não podem ser captu-
29
rados por profilers tradicionais, pois as rotinas que são crı́ticas para a percepção
temporal do usuário de uma aplicação são, em geral, chamadas poucas vezes. As
falhas de desempenho, nesse caso, são devidas a operações de entrada e saı́da
necessárias às complexas interações entre usuário, aplicação, e dispositivos de
hardware. Ainda em termos de profiling, Nistor et al. produziram uma ferramenta que detecta acessos repetitivos sobre as mesmas posições de memória.
Essa ferramenta foi usada com grande efetividade, revelando diversos problemas
de eficiência antes desconhecidos em software de uso industrial. Uma análise
dinâmica similar a de Nistor et al., dessa vez descrita por Chabbi et al. [3], levou
a descoberta do problema que mostramos na figura 3.
Todos esses recentes trabalhos relacionam-se à discussão iniciada por Jin
et al. [10], e têm em comum o fato de serem baseados em análises dinâmicas
de código. Ao contrário desses trabalhos, nosso artigo usa somente técnicas
estáticas. Dentre as pesquisas que conhecemos, aquela que julgamos a mais
próxima da nossa foi publicada por St-Amour et al. [18]. O grupo de St-Amour
projetou um compilador que auxilia o desenvolvedor em seu trabalho, propondolhe sugestões de codificação que podem habilitar otimizações de código mais
agressivas. Essa ferramenta não é automática, pois demanda respostas do usuário
que desempenha o papel de programador. Nossas técnicas, por outro lado, são
completamente autônomas, não necessitando de qualquer tipo de intervenção.
5
Considerações Finais
Neste artigo, nós descrevemos dois bugs de desempenho, e propusemos duas otimizações baseadas na clonagem de funções para saná-los. A primeira de nossas
otimizações lida com funções cujo valor de retorno não é usado. A segunda delas promove a distinção dos apontadores passados como parâmetros de funções.
Nossas otimizações são dependentes do contexto em que as funções são chamadas. Assim, para aplicá-las somente nos contextos promissores, nós recorremos
à clonagem de funções. Nossos experimentos mostraram que os dois bugs de
desempenho que descrevemos neste artigo são muito comuns, mesmo em programas usados pela comunidade de alto desempenho. Esses experimentos mostraram, ainda, que nossas transformações são capazes de aumentar a eficiência
de programas, ainda que aplicadas sobre os nı́veis mais altos de otimização de
um compilador industrial. É nossa intenção continuar desenvolvendo outras otimizações baseadas em clonagem que sejam sensı́veis ao contexto de chamada das
funções. Como próximos alvos, vislumbramos a eliminação de parâmetros não
usados de procedimentos e a eliminação de escritas redundantes em memória.
Software: estamos atualmente trabalhando na submissão de nossas técnicas
como um patch para LLVM. Todo o código utilizado em nossos experimentos encontra-se publicamente disponı́vel na página https://code.google.com/
p/clone-based-opts/.
30
Referências
1. Lars Ole Andersen. Program Analysis and Specialization for the C Programming
Language. PhD thesis, DIKU, University of Copenhagen, 1994.
2. Andrew W. Appel and Jens Palsberg. Modern Compiler Implementation in Java.
Cambridge University Press, 2nd edition, 2002.
3. Milind Chabbi and John Mellor-Crummey. Deadspy: a tool to pinpoint program
inefficiencies. In CGO, pages 124–134. ACM, 2012.
4. Igor Rafael de Assis Costa, Pericles Rafael Oliveira Alves, Henrique Nazare Santos,
and Fernando Magno Quintao Pereira. Just-in-time runtime specialization. In
CGO, pages 1–11. ACM, 2013.
5. Edsger W. Dijkstra. Letters to the editor: go to statement considered harmful.
Commun. ACM, 11(3):147–148, 1968.
6. Dick Grune, Kees van Reeuwijk, Henri E. Baland Ceriel J. H. Jacobs, and Koen
Langendoen. Modern Compiler Design. Springer, 2nd edition, 2012.
7. Mary Wolcott Hall. Managing interprocedural optimization. PhD thesis, Rice
University, Houston, TX, USA, 1991. UMI Order No. GAX91-36029.
8. Ben Hardekopf and Calvin Lin. The ant and the grasshopper: fast and accurate
pointer analysis for millions of lines of code. In PLDI, pages 290–299. ACM, 2007.
9. Reid Holmes and Robert J. Walker. Systematizing pragmatic software reuse. ACM
Trans. Softw. Eng. Methodol., 21(4):20:1–20:44, 2013.
10. Guoliang Jin, Linhai Song, Xiaoming Shi, Joel Scherpelz, and Shan Lu. Understanding and detecting real-world performance bugs. In PLDI, pages 77–88. ACM,
2012.
11. Milan Jovic, Andrea Adamoli, and Matthias Hauswirth. Catch me if you can:
performance bug detection in the wild. In OOPSLA, pages 155–170. ACM, 2011.
12. Linda Torczon Keith D. Cooper. Engineering a Compiler. Morgan Kaufmann, 2nd
edition, 2012.
13. Charles W. Krueger. Software reuse. ACM Comput. Surv., 24(2):131–183, 1992.
14. William Landi and Barbara G. Ryder. Pointer-induced aliasing: a problem classification. In POPL, pages 93–103. ACM, 1991.
15. Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong
program analysis & transformation. In CGO, pages 75–88. IEEE, 2004.
16. Ondřej Lhoták and Laurie Hendren. Context-sensitive points-to analysis: is it
worth it? In CC, pages 47–64. Springer-Verlag, 2006.
17. Olin Shivers. Control-flow analysis in Scheme. In PLDI, pages 164–174. ACM,
1988.
18. Vincent St-Amour, Sam Tobin-Hochstadt, and Matthias Felleisen. Optimization
coaching: optimizers learn to communicate with programmers. In OOPSLA, pages
163–178. ACM, 2012.
19. John Whaley and Monica S. Lam. Cloning-based context-sensitive pointer alias
analysis using binary decision diagrams. In PLDI, pages 131–144. ACM, 2004.
31
Prevenção de Ataques de Não-Terminação
Baseados em Estouros de Precisão
Raphael Ernani Rodrigues and Fernando Magno Quintão Pereira
Departamento de Ciência da Computação – UFMG – Brasil
{raphael,fernando}@dcc.ufmg.br
Resumo Dizemos que um programa é vulnerável a um ataque de não
terminação quando um adversário pode lhe fornecer valores de entrada
que façam algum de seus laços iterar para sempre. A prevenção de ataques desse tipo é difı́cil, pois eles não se originam de bugs que infringem
a semântica da linguagem em que o programa foi feito. Ao contrário,
essas vulnerabilidades têm origem na aritmética modular inteira de linguagens como C, C++ e Java, que possui semântica bem definida. Neste
artigo nós apresentamos uma ferramenta que detecta tais problemas, e
que saneia código vulnerável. A detecção da vulnerabilidade dá-se via
uma análise de fluxo de informação; a sua cura decorre de guardas que
nosso compilador insere no código vulnerável. Nós implementamos esse
arcabouço em LLVM, um compilador de qualidade industrial, e testamo-no em um conjunto de programas que compraz mais de 2.5 milhões
de linhas de código escrito em C. Descobrimos que, em média, caminhos
em que informação perigosa trafega são pequenos, sendo compostos por
não mais que 13 instruções assembly. A instrumentação que inserimos
para prevenir ataques de não terminação aumenta o tamanho do programa saneado em cerca de 5% em média, e torna-os menos que 1%
mais lentos.
Abstract. We say that a program is vulnerable to a non-termination
attack if it contains a loop that is bounded by values dependent on public inputs, and an adversary can manipulate these values to force this
loop to iterate forever. Preventing this kind of attack is difficult because
it does not originate from bugs that break the semantics of the programming language, such as buffer overflows. Instead, they usually are
made possible by the wrapping integer arithmetics used by C, C++ and
Java-like languages, which have well-defined semantics. In this paper we
present a diagnosis and a solution for this type of attack. Firstly, we
describe a tainted-flow analysis that detects non-termination vulnerabilities. Secondly, we provide a compiler transformation that inserts arithmetic guards on loop conditions that may not terminate due to integer
overflows. We have implemented our framework in the LLVM compiler,
and have tested it on a benchmark suite containing over 2.5 million lines
of C code. We have found out that the typical path from inputs to loop
conditions is, on the average, less than 13 instructions long. Our instrumentation that prevents this kind of attack adds on average less than 5%
extra code on the secured programs and make them less than 1% slower
than the original, unprotected programs.
32
1
Introdução
Um ataque de Negação de Serviços (Denial-of-Service – DoS) consiste em sobrecarregar um servidor com uma quantidade de falsas requisições grande o suficiente para lhe comprometer a capacidade de atender contatos legı́timos. Existem
hoje diversas maneiras diferentes de detectar e reduzir a efetividade desse tipo
de ataque [15]. Neste artigo, contudo, descreveremos uma forma de negação de
serviço que é de difı́cil detecção: os ataques de não-terminação. Um adversário
realiza um ataque desse tipo fornecendo ao programa alvo entradas cuidadosamente produzidas para forçar iterações eternas sobre um laço vulnerável. Um
ataque de não terminação demanda conhecimento do código fonte do sistema a
ser abordado. Não obstante tal limitação, esse tipo de ataque pode ser muito
efetivo, pois bastam algumas requisições para comprometer o sistema alvo. Uma
vez que essa quantidade de incursões é pequena, os métodos tradicionais de detecção de negação de serviço não podem ser usados para reconhecer ataques de
não-terminação. Além disso, dada a vasta quantidade de código aberto usado
nos mais diversos ramos da indústria de software, usuários maliciosos têm à sua
disposição um vasto campo de ação.
A detecção de código vulnerável a ataques de não-terminação é difı́cil. Tal
dificuldade existe, sobretudo, porque esse tipo de ataque não decorre de deficiências de tipagem fraca, normalmente presentes em programas escritos em C
ou C++. Programas escritos em linguagens fortemente tipadas, como Java, por
exemplo, também apresentam a principal fonte de vulnerabilidades a ataques de
não terminação: a aritmética modular inteira. Em outras palavras, uma operação
como a + 1, em Java, C ou C++, pode resultar em um valor menor que aquele
inicialmente encontrado na variável a. Esse fenômeno ocorrerá quando a variável
a guardar o maior inteiro presente em cada uma dessas linguagens. Nesse caso,
ao fim da operação, a + 1 representará o menor inteiro possı́vel em complemento
de dois. Em outras palavras, um laço como for (i = 0; i <= N; i++) nunca
terminará se N for MAX INT, o maior inteiro da linguagem.
Este artigo traz duas contribuições relacionadas a ataques de não-terminação.
Em primeiro lugar, ele descreve uma técnica que descobre vulnerabilidades relacionadas a esse tipo de ataque. Em segundo lugar, o artigo mostra como código
pode ser protegido contra tais ataques. A nossa técnica de detecção de vulnerabilidades é baseada em análise de fluxo contaminado. Tal análise é parte do arcabouço teórico de rastreamento de informação inicialmente proposto por Denning
e Denning nos anos setenta [8]. Um ataque de fluxo contaminado pode ser efetivo
somente em programas cujas operações crı́ticas dependam de dados de entrada.
Em nosso contexto, uma operação crı́tica é o teste de controle de laço. Em conjunto com o algoritmo de detecção de vulnerabilidades, nós propomos também
uma técnica para sanear programas contra ataques de não-terminação. Nossa
estratégia consiste na inserção de verificações sobre as operações aritméticas
realizadas pelo programa alvo. Essas verificações ocorrem durante a execução
do programa, e invocam código de segurança sempre que estouros de precisão
em variáveis inteira são percebidos. Nós instrumentamos somente código que
controla o número de iterações em laços. Consequentemente, o arcabouço que
33
propomos incorre em uma perda de desempenho muito pequena, e, em nossa
opinião, completamente justificável em decurso do benefı́cio que assegura.
Implementamos todas as ideias que discutimos neste artigo em LLVM, um
compilador de qualidade industrial [13]. Na seção 4 descreveremos uma série de
experimentos que validam nossa análise. Examinando os programas presentes
na coleção SPEC CPU 2006, fomos capazes de descobrir 12.304 laços que são
influenciados por dados provenientes de entradas públicas, isto é, que podem ser
manipuladas por um adversário. Pelo menos 920 desses laços estão sujeitos à não
terminação. Esse número advém de um padrão simples: procuramos por laços
cujo teste de parada é do tipo i <= N, sendo N dependente da entrada. Uma vez
que nos atemos a esse tipo de condição de parada, especulamos que a quantidade
de laços vulneráveis presente nos programas de SPEC CPU 2006 seja bem maior
que o valor que apuramos. Para testar essa hipótese, alargamos a nossa definição
de laços vulneráveis para englobar qualquer iterador cuja condição de controle
esteja sujeita a estouro de precisão. Dentre os laços encontrados em SPEC CPU
2006, 7,742 deles atendem esse requisito. A nossa instrumentação – usada para
impedir os ataques de não-terminação – mostra-se extremamente eficiente. Os
testes que inserimos antes de cada operação aritmética que pode levar a um ataque de não terminação custa-nos uma perda de desempenho que vai de 0.61%
no pior caso, a 0.24% no melhor. Protegemos laços conservadoramente. Assim,
ainda que não estejamos fornecendo uma prova formal de que um laço é vulnerável, nós garantimos que qualquer programa instrumentado é invulnerável a
ataques de não-terminação baseados em estouro de precisão.
2
Ataques de Não-Terminação
De acordo com Appel e Palsberg [2, p.376], um laço natural é um conjunto de
nós S do grafo de fluxo de controle (CFG) de um programa, includindo um nó
cabeçalho H, com as seguintes três propriedades:
– a partir de qualquer nó em S existe um caminho que chega a H;
– existe um caminho de H até qualquer nó que faz parte de S;
– qualquer caminho de um nó fora de S para um nó em S contém H.
A condição de parada de um laço é uma expressão booleana E = f (e1 , e2 , . . . , en ),
sendo cada ej , 1 ≤ j ≤ n um valor que contribui para a computação de E. Seja
P um programa que possui um laço L limitado por uma condição de parada E =
f (e1 , e2 , . . . , en ). Dizemos que P é vulnerável a um ataque de não terminação
quando as duas condições abaixo são verdadeiras sobre ele:
1. existe um subconjunto E 0 ⊆ {e1 , e2 , . . . , en } de valores que dependem de um
conjunto I = {i1 , i2 , . . . , im } de dados lidos a partir da entrada do programa.
2. existe uma atribuição de valores i1 7→ v1 , i2 7→ v2 , . . . , im 7→ vm que, ao
influenciar E 0 , faz com que E nunca tenha um valor que faça o laço L parar.
Note que a nossa definição de vulnerabilidade de não-terminação requer a noção
de dependência de dados. Se um programa P possui uma instrução que usa a
34
(a)
1
2
3
4
5
6
7
8
9
(b)
int fact(int n) {
int r = 1;
int i = 2;
while (i <= n) {
r *= i;
i++;
}
return r;
}
1
(c)
r0 = 1
i0 = 2
1
3
r1 = ϕ(r0, r2)
i1 = ϕ(i0, i2)
p = i1 ≤ n
if p goto L7
2
3
4
5
6
7
7
r2 = r1 * i1
i2 = i1 + 1
goto L3
8
10
ret r0
9
10
11
int fact(int n) {
int r = 1;
if (n < 13) {
int i = 2;
while (i <= n) {
r *= i;
i++;
}
}
return r;
}
Figura 1. (a) Uma função em C, que calcula o fatorial de um número inteiro. (b) O
CFG da função fact. (c) Exemplo de laço cuja condição de parada depende de valores
de entrada mas que sempre termina.
variável u e define a variável v, então v depende de u. Dependências de dados são
transitivas, e embora possam ser cı́clicas, não são necessariamente comutativas.
Ilustraremos ataques de não terminação via o programa mostrado na Figura 1(a). Esse programa calcula o fatorial de um número inteiro na linguagem
C. O padrão que rege essa linguagem de programação não determina o tamanho do tipo int. Essa informação depende da implementação do compilador
usado. Entretanto, é usual que inteiros sejam representados como números de
32 bits em complemento de dois. Nesse caso, o maior inteiro representável é
MAX INT = 231 − 1 = 2, 147, 483, 647. Se o parâmetro n for igual a MAX INT ,
então a condição da linha 4 sempre será verdadeira, e o laço nunca terminará. A
não-terminação ocorre porque quando i finalmente chega a MAX INT , a soma
i + 1 nos retorna o menor inteiro possı́vel, isto é, −231 .
O programa da figura 1(a) é vulnerável a ataques de não-terminação. Para
explicitar tal fato, a figura 1(b) mostra o grafo de fluxo de controle do programa.
Esse CFG está convertido para o formato de atribuição estática única (SSA) [7].
Usaremos essa representação de programas porque ela facilita a nossa análise
de dependência de dados. Os blocos básicos que começam nos rótulos 3 e 7
formam um laço natural, segundo a definição de Appel e Palsberg. Esse laço
é controlado pela condição de parada i1 ≤ n. A variável n, o limite do laço, é
dependente da entrada. Existe um valor de n, a saber MAX INT , que força o
laço a não-terminar.
3
Detecção e Prevenção de Não-Terminações
Nesta seção descreveremos nossa técnica para detectar vulnerabilidades de nãoterminação. Esse algoritmo de detecção fornece os subsı́dios necessários a uma
segunda técnica que introduzimos neste artigo: o saneamento de laços.
35
p
≤
++
i1
i2
ϕ
n
i0
r1
ϕ
r0
*
r2
=
=
2
1
Figura 2. (a) Grafo de dependências da função fact, construı́do a partir do CFG visto
na figura 1(b).
3.1
Detecção Automática de Não-Terminação
Dizemos que um laço é alcançável quando as condições que o controlam usam
valores que dependem de dados de entrada do programa. Note que um laço alcançável não é necessariamente vulnerável. A tı́tulo de exemplo, o programa da
Figura 1(c), uma sutil alteração da função fact inicialmente vista na figura 1(a),
termina para qualquer entrada, embora ele contenha um laço alcançável. Utilizamos o grafo de dependências de dados para determinar laços alcançáveis. Esse
grafo é definido da seguinte forma: para cada variável v no programa, nós criamos um nó nv , e para cada instrução i no programa, nós criamos um nó ni . Para
cada instrução i : v = f (. . . , u, . . .) que define uma variável v e usa uma variável
u nós criamos duas areastas: nu → ni e ni → nv . O grafo de dependências que
extraı́mos a partir do CFG visto na figura 1(b) é mostrado na figura 2.
Um caminho entre uma entrada do programa e o predicado que controla o
laço é uma condição necessária para um ataque de não-terminação. O grafo de
dependências de nosso exemplo apresenta tal condição: existe um caminho que
une o nó correspondente ao parâmetro n, uma entrada, ao nó que corresponde
a p, o predicado de controle do laço. Esse tipo de caminho, uma vez construı́do
o grafo, pode ser encontrado em tempo linear no número de arestas do grafo normalmente proporcional ao número de nós - via uma simples busca em profundidade ou largura.
Diremos que um laço é vulnerável quando ele é alcançável, e, além disso, sua
condição de parada é dependente de alguma operação cı́clica passı́vel de estouro
de precisão. Seguindo a definição de laços de Appel e Palsberg, uma operação
cı́clica é qualquer instrução que ocorre no corpo S do laço. Por exemplo, no CFG
da figura 1(b), as instruções i2 = i1 + 1 e r2 = r1 × i1 são cı́clicas. O laço daquele
exemplo encaixa-se em nossa definição de vulnerabilidade, pois sua condição de
parada é alcançável a partir da entrada, e depende de uma instrução cı́clica
passı́vel de estouro de precisão: i2 = i1 + 1.
A nossa definição de vulnerabilidade inclui muitos laços que não são concretamente vulneráveis, tais como aquele visto na figura 1(c). Seria possı́vel utilizar
técnicas computacionalmente intensivas, tais como algoritmos de satisfabilidade,
36
para refinar a nossa definição, eliminando alguns desses falsos positivos. Tal
abordagem já foi utilizada em trabalhos anteriores ao nosso [4,6,11,18,20]. Por
outro lado, os próprios autores desses trabalhos reportam que dificilmente suas
técnicas poderiam lidar com programas muito grandes. Nós optamos por usar
uma definição mais conservadora de laço vulnerável para termos uma ferramenta
prática. Nós sanearemos todo laço considerado perigoso, inclusive aqueles que,
devido à nossa definição liberal de vulnerabilidade, de fato não o são. Ainda
assim, conforme mostraremos na seção 4, o impacto dessa instrumentação é negligı́vel.
3.2
Saneamento de Laços
Uma vez encontrado um caminho vulnerável, passamos à fase de saneamento
de laços. Um laço pode ser saneado via a inserção de testes que detectam e
tratam a ocorrência de estouros de precisão inteira. Nós inserimos tais testes
sobre as operações aritméticas cı́clicas que controlam a condição de parada do
laço. Continuando com o nosso exemplo, o laço alvo possui dois blocos básicos:
o primeiro começa no rótulo três, e o segundo começa no rótulo sete. O laço
possui duas operações aritméticas cı́clicas, todas ocorrendo no segundo bloco
básico. Dentre essas operações, aquela no rótulo sete é inofensiva: ela define a
variável r2 , que não participa da condição de parada do laço. Por outro lado,
a operação no rótulo oito, que define a variável i2 , é usada no cálculo daquela
condição, e precisa ser instrumentada.
Novamente, o grafo de dependências ajuda-nos a encontrar quais operações
precisam ser instrumentadas para sanear um laço controlado por um predicado
p. Nesse caso, usamos o seguinte critério para determinar se uma operação i :
v = f (v1 , . . . , vn ) precisa ser instrumentada:
– Existe um caminho no nó ni até o nó np .
– O nó ni encontra-se em um ciclo.
– A operação que define a variável i pode provocar um estouro aritmético.
A tı́tulo de exemplo, a operação de incremento ++ no grafo de dependências
visto na figura 2 precisa ser instrumentada. Em primeiro lugar, porque essa
operação encontra-se em um ciclo. Em segundo lugar, porque existe um caminho
do nó n++ até o nó np .
Instrumentação de Saneamento. Para evitar que estouros de precisão venham
a causar a não-terminação de laços, nós inserimos testes no código binário do
programa alvo. O código que constitui cada um desses testes é formado por uma
guarda, mais um tratador de eventos. Nossas guardas usam as condições mostradas na figura 3 para verificar a ocorrência de estouros de precisão. Atualmente
instrumentamos quatro tipos diferentes de instrução: adição, subtração, multiplicação e arredamentos para a esquerda, conhecidos como shift left. As operações
de adição, subtração e multiplicação podem ser com ou sem sinal aritmético.
Os testes são implementados como sequências de operações binárias, executados logo após a instrução guardada. Para ilustrar esse ponto, mostramos, na
37
Instrução
Verificação
x = o1 + s o2
(o1 > 0 ∧ o2 > 0 ∧ x < 0) ∨
(o1 < 0 ∧ o2 < 0 ∧ x > 0)
x = o1 + u o2
x < o1 ∨ x < o2
x = o1 − s o2
(o1 < 0 ∨ o2 > 0 ∨ x > 0) ∨
(o1 > 0 ∨ o2 < 0 ∨ x < 0)
x = o1 − u o2
o1 < o 2
x = o1 ×u/s o2 x 6= 0 ⇒ x ÷ o1 6= o2
x = o1 M n
(o1 > 0 ∧ x < o1 ) ∨ (o1 < 0 ∧ n 6= 0)
x = ↓n o1
cast(x, type(o1 )) 6= o1
Figura 3. Overflow checks. Usamos ↓n para descrever a operação que trunca em n
bits. O subscrito s indica uma operação aritmética com sinal, e o subscrito u indica
uma operação sem sinal.
figura 4, o código necessário para instrumentar uma soma com sinal de duas
variáveis. Essa figura mostra código no formato intermediário usado por LLVM,
o compilador que utilizamos para implementar as idéias descritas neste artigo.
Omitimos, nesse exemplo, o código do tratador de evento de estouro, pois ele simplesmente invoca uma rotina implementada em uma biblioteca dinamicamente
compartilhada. Conforme podemos observar pela figura, uma guarda aumenta
o código instrumentado substancialmente. Nesse exemplo em particular a verificação requer a inserção de 14 novas instruções no programa guardado. Embora
tal crescimento a princı́pio possa parecer proibitivamente grande, os experimentos que mostraremos na seção 4 indicam que somente uma parcela muito pequena
das instruções do programa alvo precisam ser guardadas. Consequentemente, o
custo, em termos de crescimento de código e perda de desempenho, é negligı́vel.
4
Resultados Experimentais
Nós implementamos as técnicas descritas neste artigo em LLVM versão 3.3.
Nossa implementação foi testada em uma máquina Intel® Core™ i7-3770, com 16
Gigabtyes de RAM, e 3.40 GHz de Clock. Executamos nossa análise com sucesso
sobre o arcabouço de testes do LLVM, um conjunto de programas com mais de
4.3 milhões de linhas de código C. No restante desta seção mostraremos somente
resultados obtidos sobre os programas escritos na linguagem C disponı́veis em
SPEC CPU 2006.
Definição de Entrada de Dados. As entradas de dados são as funções que
um adversário pode usar para forçar a não-terminação de um programa. Nos
38
(a)
int foo(int x, int y) {
return x + y;
}
(b)
entry:
%add = add nsw i32 %x, %y
ret i32 %add
(e)
entry:
%add = add nsw i32 %x, %y
%0 = icmp sge i32 %x, 0
%1 = icmp sge i32 %y, 0
%2 = and i1 %0, %1
%3 = icmp slt i32 %add, 0
%4 = and i1 %2, %3
%5 = icmp slt i32 %x, 0
%6 = icmp slt i32 %y, 0
%7 = and i1 %5, %6
%8 = icmp sge i32 %add, 0
%9 = and i1 %7, %8
%10 = or i1 %4, %9
br i1 %10, label %11, label %12
(c)
%11:
call void %handle_overflow(...)
br label %12
(d)
%12:
ret i32 %add
Figura 4. (a) Programa que será instrumentado. (b) Representação do programa em
bytecodes LLVM. (c) Operação que está sendo instrumentada. (d) Teste de detecção
de estouro de precisão. (e) Programa instrumentado, em bytecodes LLVM.
experimentos apresentados nesta seção, consideraremos como entrada de dados
os seguintes valores:
– os argumentos do método main, isto é, as variáveis argc e argv;
– o resultado retornado por funções externas;
– ponteiros passados como argumento de funções externas.
As funções externas são a união dos seguintes três conjuntos:
– funções que não foram declaradas em nenhum dos arquivos que compõem o
programa compilado;
– funções sem corpo;
– funções que podem ser chamadas via um ponteiro de funções.
Grafo de dependências de dados. A figura 5 mostra informações estáticas
a respeito dos grafos de dependências dos programas analisados. Como ponto
de referência, mostramos o tamanho absoluto de cada programa, em número
de instruções. Em média, 14% dos valores que cada programa manipula podem
conter informações vindas da entrada de dados. Esses valores são produzidos
por funções externas, para as quais não é possı́vel saber se há ou não contaminação por dados externos. Observa-se que existem mais nós de operação no
grafo do que instruções no programa. Esse fato verifica-se porque nossa análise é
interprocedural. Assim, inserimos nós de operação para criar dependências entre
39
Benchmark
433.milc
444.namd
447.dealII
450.soplex
470.lbm
400.perlbench
401.bzip2
403.gcc
429.mcf
445.gobmk
456.hmmer
458.sjeng
462.libquantum
464.h264ref
471.omnetpp
473.astar
483.xalancbmk
Total
Insts.
Entr.
Ops.
Vars.
Mems.
Arestas
24,971
77,922
483,614
67,808
3,788
288,429
17,999
830,861
2,851
146,298
62,704
25,473
6,562
141,772
96,929
9,386
648,941
3,995
15,964
98,180
11,182
239
25,224
1,862
65,118
373
21,420
8,487
2,610
921
11,995
15,989
1,506
132,976
24,799
78,043
512,374
69,870
3,787
287,050
18,007
830,054
2,897
152,342
63,004
25,169
6,552
141,606
101,197
9,476
689,176
20,435
72,866
441,576
56,172
3,490
230,982
15,019
660,772
2,354
167,197
51,549
26,313
5,845
106,292
88,819
8,199
569,780
6,901
10,468
131,986
21,764
626
98,886
4,423
321,279
905
21,146
20,727
2,522
940
45,219
31,686
1,982
244,874
74,599
232,792
1,516,202
204,159
10,859
819,872
53,414
2,440,279
8,608
458,405
182,736
73,355
19,142
409,813
305,170
28,067
1,971,945
2,936,308
418,041
3,015,403
2,527,660
966,334
8,809,417
Figura 5. Dados do grafo de dependência dos programas analisados. Insts.: número de
instruções do programa. Entr.: número de instruções que podem representar entradas
de dados. Ops.: número de nós de operação no grafo de dependência. Vars.: número
de nós que representam variáveis. Mems.: número de nós que representam blocos de
memória. Arestas: número de arestas do grafo.
parâmetros formais e parâmetros reais e também para ligar valores de retorno
aos valores que recebem o resultado de funções.
A figura 5 também apresenta a quantidade de nós de memória. Esses nós são
vértices do grafo de dependência que representam os ponteiros e os blocos de
memória alocados no código do programa. A fim de determinar se dois ponteiros
são sinônimos ou não, implementamos a análise de apontadores de Andersen [1].
Sinônimos, isto é, apontadores que indicam regiões de memória sobrepostas, são
agrupados em um mesmo nó. Quanto mais precisa a análise de ponteiros, menores
os conjuntos contidos em cada uma dessas unidades. A análise de Andersen é
um compromisso entre eficiência e precisão.
Analisando a figura 5, constatamos que os grafos de dependências são esparsos. Nos programas de SPEC CPU 2006, a razão entre o número de vértices e
o número de arestas é 1.38. Essa relação fica ainda mais evidente quando extraı́mos o coeficiente de determinação entre essas duas grandezas – número de
vértices e arestas. Obtemos o valor de 0.99, o que indica uma forte correlação
40
Benchmark
433.milc
444.namd
447.dealII
450.soplex
470.lbm
400.perlbench
401.bzip2
403.gcc
429.mcf
445.gobmk
456.hmmer
458.sjeng
462.libquantum
464.h264ref
471.omnetpp
473.astar
483.xalancbmk
Total
Laços (L)
Alcançáveis
Caminhos
Vulneráveis
I
II
% (II/L)
329
484
4,759
542
18
1,160
211
3,824
39
1,082
681
235
79
1,614
363
88
2,212
146
438
3,493
513
0
1,034
151
2,966
10
588
376
139
44
193
280
53
1,880
25
9
12
14
0
14
19
24
7
17
8
15
10
17
8
8
10
138
408
2,657
453
0
315
95
1,297
2
499
255
109
41
161
201
50
1,061
0
2
73
175
0
72
24
310
0
25
84
2
3
9
41
18
82
0.00%
0.41%
1.53%
32.29%
0.00%
6.21%
11.37%
8.11%
0.00%
2.31%
12.33%
0.85%
3.80%
0.56%
11.29%
20.45%
3.71%
17,720
12,304
13
7,742
920
5.19%
Figura 6. Informações estáticas inferidas pela análise de não-terminação. Laços:
número de laços no programa. Alcançáveis: quantidade de laços que são dependentes
de dados produzidos a partir de canais de entrada. Caminhos: tamanho médio do menor caminho de dependência de dados da entrada até a operação de controle do laço.
Vulneráveis: número de laços que preenchem nossos requisitos de vulnerabilidade. I:
laços vulneráveis segundo a definição da seção 3.1. II: laços vulneráveis controlados
por comparações do tipo i <= N.
linear entre os dois valores. Essa baixa densidade ocorre porque em programas
reais variáveis tendem a ser usadas um número baixo de vezes. Boissinot et al. [3]
demonstraram, empiricamente, que a maior parte das variáveis é usada somente
uma vez no programa, e mais de 99% das variáveis são usadas menos que cinco
vezes. Assim, a maior parte dos vértices que representam variáveis em nossos
grafos de dependências possuem grau de saı́da inferior a cinco.
Laços Alcançáveis e Vulneráveis. A figura 6 mostra a quantidade de laços
alcançáveis e vulneráveis que encontramos por programa. A noção de “laço vulnerável”é definida na seção 3.1. A quantidade de laços vulneráveis que reportamos representa um limite inferior no número de estruturas de iteração que
precisamos instrumentar para prevenir ataques de não terminação baseados em
estouro de precisão. A figura indica que aproximadamente 70% de todos os laços
41
Benchmark
433.milc
444.namd
447.dealII
450.soplex
470.lbm
400.perlbench
401.bzip2
403.gcc
429.mcf
445.gobmk
456.hmmer
458.sjeng
462.libquantum
464.h264ref
471.omnetpp
473.astar
483.xalancbmk
Total
Insts.
Arits.
Instrumentação
Crescimento
I
II
I
II
24,971
77,922
483,614
67,808
3,788
288,429
17,999
830,861
2,851
146,298
62,704
25,473
6,562
141,772
96,929
9,386
648,941
1,101
3,136
14,910
1,779
1,130
7,983
1,684
14,338
158
11,856
3,210
2,138
593
13,398
2,029
639
12,528
150
932
3,762
771
0
655
240
2,072
4
932
419
167
68
411
249
99
1,562
0
2
77
261
0
226
56
473
0
76
143
22
4
102
46
37
116
9.49%
15.75%
6.40%
17.83%
0.00%
2.92%
17.20%
3.26%
2.00%
9.73%
10.08%
9.97%
14.49%
3.81%
3.91%
16.46%
2.52%
0.00%
0.04%
0.21%
6.09%
0.00%
1.09%
4.61%
0.83%
0.00%
0.78%
3.37%
1.31%
0.98%
0.88%
0.73%
6.13%
0.24%
2,936,308
92,610
12,493
1,641
5.02%
0.81%
Figura 7. Impacto da instrumentação no código saneado. Insts.: número de instruções
no benchmark. Arits.: número de instruções que podem causar estouro de precisão inteira. Instrumentação: quantidade de testes inseridos para sanear o programa. Crescimento: razão entre o tamanho do programa instrumentado e o tamanho do programa
original. I: análise considerando todos os laços vulneráveis. II: análise considerando somente os laços controlados por condições do tipo i <= N.
do programa são alcançáveis. Dessa quantidade, metade é vulnerável. Cerca de
12% dos laços vulneráveis são controlados por comparações do tipo i <= N. Esse
tipo de condição é particularmente perigosa, pois, conforme visto no exemplo da
figura 1, se o limite N for o maior inteiro possı́vel, então a condição será sempre verdade. A figura 6 mostra que os caminhos entre as entradas de dados e
as condições de parada de laços são geralmente pequenos. Por exemplo, os dez
caminhos vulneráveis em 429.mcf possuem em média sete instruções. Conclui-se
que um auditor que procure por vulnerabilidades a ataques de não-terminação
tem, em geral, de analisar sequências relativamente pequenas de código.
Instrumentação. A figura 7 mostra que nossa instrumentação tem um impacto
ı́nfimo sobre o tamanho do programa guardado. Nossos programas possuem poucas operações de tipo inteiro passı́veis de estouro de precisão – em média somente
3.15% das instruções são desse tipo. Dessas instruções, um número ainda me-
42
0.04 0.02 0 ‐0.02 ‐0.04 1.
bz
ip
2 m
4.
na
40
d le
x 44
so
p
m
3.
er
ilc
0.
45
43
m
re
f 64
6.
hm
45
m
46
4.
h2
0.
lb
47
m
an
tu
qu
2.
lib
8.
sje
ng
45
cf
42
9.
m
II as
ta
r
3.
47
de
al
7.
44
46
47
1.
om
ne
tp
p ‐0.06 Todos os laços vulneráveis Somente laços limitados por <= Figura 8. Variação no tempo de execução dos programas instrumentados.
nor é usado dentro de laços vulneráveis. No caso médio, cada laço vulnerável
custou-nos a criação de 1.64 guardas, como aquela vista na figura 4(e). O aumento de tamanho do programa guardado é pequeno, conforme podemos observar nas duas últimas colunas da figura 7. O maior crescimento, observado
em 450.soplex, foi de 17.83%. Na média, entretanto, os programas cresceram
apenas 5% em número de instruções. Um dos benchmarks, 470.lbm não recebeu
qualquer instrumentação, uma vez que ele não possui laços controlados por dados de entrada. Todos os laços desse benchmark dependem de constantes criadas
dentro do próprio programa.
Tempo de execução. Uma vez que o número de instruções inseridas nos
programas é tão pequeno, o crescimento de seu tempo de execução é irrisório.
Além disso, nenhuma das instruções presentes em uma guarda realiza operações
demoradas, como acesso a memórias lentas. Executamos todos os programas instrumentados, passando-lhes suas entradas de referência, conforme especificado
no manual de uso de SPEC CPU 2006, e as diferenças de tempo de execução
são mostradas na figura 8. Cada programa foi amostrado 30 vezes, e o resultado
que apresentamos é a média aritmética dessas trinta amostras. A margem de
erro é negligı́vel. Testamos dois modos de instrumentação. No primeiro deles
guardamos todos os laços considerados vulneráveis contra estouros de precisão.
Nesse caso, observamos que os programas instrumentados ficaram 0.61% mais
lentos. No segundo modo de instrumentação guardamos somente os laços cujas
condições de controle usam comparadores do tipo <=. Registramos nesse segundo
experimento que os programas modificados ficaram 0.24% mais lentos. Caso
houvéssemos instrumentado todas as operações aritméticas nos programas disponı́veis em SPEC CPU 2006, a taxa de lentidão seria de 3.24%. Não mostramos
esse resultado na figura, para não comprometermos a sua leitura. Em alguns programas, como 401.bzip2, por exemplo, pudemos registrar diminuição do tempo
de execução. Não encontramos razão aparente para tal comportamento, pois não
efetuamos qualquer otimização sobre o código instrumentado.
43
5
Trabalhos Relacionados
Este trabalho aborda temas relacionados a diferentes áreas da análise estática
e dinâmica de programas, a saber: teoria de fluxo de informação, detecção de
estouros de precisão inteira e análise de não-terminação. Além disso, este trabalho utiliza o conceito de grafos de dependências, inicialmente proposto por
Ferrante et al. [10]. Em nosso caso, o grafo de dependência dá-nos a estrutura
de dados básica sobre a qual caminhos que levam à não-terminação podem ser
encontrados. Esses grafos, contudo, historicamente vêm se prestando a muitos
outros propósitos, como escalonamento de instruções, detecção de condições de
corrida e propagação de constantes, por exemplo.
Neste artigo usamos o grafo de dependências para rastrear o fluxo de informação contaminada. O rastreamento de fluxo de informação é uma grande
sub-área dentro do campo de análise estática de programas [8]. Existem duas
formas principais de rastrear a informação. Pode-se traçar o fluxo de dados a
partir de operações sigilosas até entradas que um adversário pode ler. Esse modo
de rastreamento é popularmente conhecido como detecção de vazamento de segredos [12,16]. E, no sentido inverso, pode-se traçar o fluxo de informação de
entradas que um adversário pode manipular até operações crı́ticas dentro do
programa [19]. Essa categoria inclui nosso trabalho, além de diversos outros
tipos de vulnerabilidades, tais como Injeção de Código SQL [21], Injeção de
Scripts [17] e Ataques de Estouro de Buffer [14].
Nós instrumentamos código considerado vulnerável para detectar estouros
de precisão que podem levar à não-terminação. Esses mesmos testes já foram
usados com vários outros objetivos em trabalhos anteriores. O mais importante
trabalho nessa área deve-se, provavelmente, a Brumley et al. [5]. O grupo de David Brumley desenvolveu uma ferramenta, RICH, que instrumenta cada operação
aritmética passı́vel de estouro de precisão inteira em um programa C. A principal
conclusão daquele trabalho foi que esse tipo de instrumentação não compromete
sobremaneira o desempenho do programa modificado. RICH, por exemplo, aumenta o tempo de execução dos programas instrumentados em menos que 6%
em média. Outro trabalho importante nesse campo foi publicado por Dietz et
al. [9]. Esse grupo implementou IOC, uma ferramenta que, assim como RICH,
detecta a ocorrência de estouros de precisão em operações aritméticas inteiras.
Porém, ao contrário de Brumley et al., Dietz et al. usaram sua ferramenta para
desenvolver um amplo estudo sobre a ocorrência de estouros em programas reais. Nosso trabalho difere desses outros em propósito: estamos interessados em
prevenir ataques de não terminação; e em método: nós instrumentamos somente
uma pequena parte dos programas alvo.
Finalmente, nosso trabalho relaciona-se com outros que também procuram
detectar, estaticamente, a não-terminação de programas. A maior parte desses
trabalhos utilizam análise simbólica de código para criar expressões que levem
um laço à não terminação. Exemplos desse tipo de pesquisa incluem os trabalhos
de Burnim et al. [6], Brockschmidt et al [4] e Veroyen et al. [20]. Esses trabalhos
não levam em consideração possibilidade de não-terminação devido a estouros
de precisão, tampouco procuram detectar possı́veis vulnerabilidades baseadas
44
em negação de serviço. Existem, contudo, trabalhos na linha de detecção de
não-terminação que são bastante próximos do nosso.
Um trabalho que prova não-terminação, mesmo em face de estouros de precisão deve-se à Gupta et al. [11]. Gupta, assim como os trabalhos anteriormente
relacionados, utiliza análise simbólica para provar a não-terminação de programas. A ferramenta implementada por Gupta et al., denominada TNT, é capaz
de encontrar uma expressão algébrica que leva um laço de programa a iterar para
sempre. Porém, TNT não aponta quais laços podem ser controlados a partir da
entrada do programa. Por outro lado, a ferramenta SAFERPHP, proposta por
Son et al. [18] possui exatamente esse objetivo. SAFERPHP analisa o código
de programas escritos em PHP, procurando por laços que um adversário pode
controlar, com o propósito, justamente, de evitar ataques de não-terminação.
A principal diferença entre nosso trabalho, e aquele de Son et al., é que, enquanto nossa ferramenta busca detectar a não-terminação devido à estouros de
precisão inteira, SAFERPHP considera a aritmética de precisão infinita. Além
disso, tanto SAFERPHP quanto TNT utilizam execução simbólica sobre caminhos possı́veis no programa alvo. Essa abordagem, em nossa opinião, não é
prática. Testemunho disso é o fato de tais ferramentas terem sido usadas, até a
presente data, somente para analisar programas muito pequenos.
6
Conclusão
Neste artigo nós descrevemos uma forma de ataque de negação de serviço que
busca levar o programa alvo à não-terminação. Ao contrário da literatura relacionada, ate-mo-nos a ataques baseados em estouro de precisão de aritmética de
inteiros. Esse fenômeno caracteriza linguagens como Java, C e C++. Nós definimos algumas propriedades necessárias para a efetiva realização de um ataque de
não-terminação, a saber, condição de controle controlada por adversário, e por
operações cı́clicas passı́veis de estouro de precisão. Em seguida, mostramos como
eliminar a última dessas condições via guardas inseridas pelo compilador. Finalmente, mostramos experimentalmente que nossas guardas, ainda que inseridas
conservadoramente, não comprometem o tempo de execução do programa instrumentado. Demonstramos assim que a prevenção de ataques de não-terminação
baseados em estouros de precisão é barata e efetiva.
Neste trabalho nós adotamos uma definição muito conservadora de laços
vulneráveis. De fato, muitos dos laços que indicamos como vulneráveis, em nossos
experimentos, de fato não o são. Nossa decisão foi fruto de um compromisso
entre a precisão e a eficiência: instrumentamos todos os laços possivelmente
vulneráveis, mesmo aqueles que não são perigosos, e ainda assim mantivemos
estável o tempo de execução dos programas. Por outro lado, é nossa intenção,
em trabalho futuro, estreitar essa definição de laço vulnerável, a fim de fornecer
a desenvolvedores uma ferramenta que lhes auxilie na descoberta de exemplos
de vulnerabilidades.
Software: nossas técnicas foram todas implementadas em LLVM, e estão disponı́veis publicamente na URL http://code.google.com/p/range-analysis/.
45
Referências
1. Lars Ole Andersen. Program Analysis and Specialization for the C Programming
Language. PhD thesis, DIKU, University of Copenhagen, 1994.
2. Andrew W. Appel and Jens Palsberg. Modern Compiler Implementation in Java.
Cambridge University Press, 2nd edition, 2002.
3. Benoit Boissinot, Sebastian Hack, Daniel Grund, Benoit Dupont de Dinechin, and
Fabrice Rastello. Fast liveness checking for SSA-form programs. In CGO, pages
35–44. IEEE, 2008.
4. Marc Brockschmidt, Thomas Ströder, Carsten Otto, and Jürgen Giesl. Automated detection of non-termination and nullpointerexceptions for Java Bytecode. In
FoVeOOS, pages 123–141. Springer-Verlag, 2012.
5. David Brumley, Dawn Xiaodong Song, Tzi cker Chiueh, Rob Johnson, and Huijia
Lin. RICH: Automatically protecting against integer-based vulnerabilities. In
NDSS. USENIX, 2007.
6. Jacob Burnim, Nicholas Jalbert, Christos Stergiou, and Koushik Sen. Looper:
Lightweight detection of infinite loops at runtime. In ASE, pages 161–169. IEEE,
2009.
7. Ron Cytron, Jeanne Ferrante, Barry K. Rosen, Mark N. Wegman, and F. Kenneth Zadeck. Efficiently computing static single assignment form and the control
dependence graph. TOPLAS, 13(4):451–490, 1991.
8. Dorothy E. Denning and Peter J. Denning. Certification of programs for secure
information flow. Commun. ACM, 20:504–513, 1977.
9. Will Dietz, Peng Li, John Regehr, and Vikram Adve. Understanding integer overflow in C/C++. In ICSE, pages 760–770. IEEE, 2012.
10. Jeanne Ferrante, Karl J. Ottenstein, and Joe D. Warren. The program dependence
graph and its use in optimization. TOPLAS, 9(3):319–349, 1987.
11. Ashutosh Gupta, Thomas A. Henzinger, Rupak Majumdar, Andrey Rybalchenko,
and Ru-Gang Xu. Proving non-termination. SIGPLAN Not., 43(1):147–158, 2008.
12. C. Hammer, J. Krinke, and G. Snelting. Information flow control for Java based
on path conditions in dependence graphs. In ISSSE, pages 1–10. IEEE, 2006.
13. Chris Lattner and Vikram S. Adve. LLVM: A compilation framework for lifelong
program analysis & transformation. In CGO, pages 75–88. IEEE, 2004.
14. Elias Levy. Smashing the stack for fun and profit. Phrack, 7(49), 1996.
15. David Moore, Colleen Shannon, Douglas J. Brown, Geoffrey M. Voelker, and Stefan
Savage. Inferring internet denial-of-service activity. ACM Trans. Comput. Syst.,
24(2):115–139, 2006.
16. Gabriel Silva Quadros and Fernando Magno Quintao Pereira. Static detection of
address leaks. In SBSeg, pages 23–37, 2011.
17. Andrei Alves Rimsa, Marcelo D’Amorim, and Fernando M. Q. Pereira. Efficient
static checker for tainted variable attacks. In SBLP. SBC, 2010.
18. Sooel Son and Vitaly Shmatikov. SAFERPHP: finding semantic vulnerabilities in
PHP applications. In PLAS, pages 8:1–8:13. ACM, 2011.
19. Omer Tripp, Marco Pistoia, Stephen Fink, Manu Sridharan, and Omri Weisman.
TAJ: Effective taint analysis of web applications. In PLDI, pages 87–97. ACM,
2009.
20. Helga Velroyen and Philipp Rümmer. Non-termination checking for imperative
programs. In TAP, pages 154–170. Springer-Verlag, 2008.
21. Gary Wassermann and Zhendong Su. Sound and precise analysis of web applications for injection vulnerabilities. In PLDI, pages 32–41. ACM, 2007.
46
FULL PAPERS (LECTURE NOTES IN COMPUTER
SCIENCE VOL. 8129)
EXCEPTION HANDLING FOR ERROR REPORTING IN PARSING EXPRESSION GRAMMARS
André Murbach Maidl (PUC-Rio), Fabio Mascarenhas (UFRJ), and Roberto Ierusalimschy (PUC-Rio)
Parsing Expression Grammars (PEGs) are a new formalism to describe a top-down parser of a language.
However, error handling techniques that are often applied to top-down parsers are not directly
applicable to PEGs. This problem is usually solved in PEGs using a heuristic that helps to simulate the
error reporting technique from top-down parsers, but the error messages are generic. We propose the
introduction of labeled failures to PEGs for error reporting, as labels help to produce more meaningful
error messages. The labeled failures approach is close to that of generating and handling exceptions
often used in programming languages, being useful to annotate and label grammar pieces that should
not fail. Moreover, our approach is an extension to the PEGs formalism that is expressive enough
to implement some previous work on parser combinators. Finally, labeled failures are also useful to
compose grammars preserving the error messages of each separate grammar.
Link: http://link.springer.com/chapter/10.1007/978-3-642-40922-6_1
LUAROCKS - A DECLARATIVE AND EXTENSIBLE PACKAGE MANAGEMENT SYSTEM
FOR LUA
Hisham Muhammad (PUC-Rio), Fabio Mascarenhas (UFRJ), and Roberto Ierusalimschy (PUC-Rio)
While sometimes dismissed as an operating systems issue, or even a matter of systems administration,
module management is deeply linked to programming language design. The main issues are how to
instruct the build and runtime environments to find modules and handle their dependencies; how to
package modules into redistributable units; how to manage interaction of code written in different
languages; and how to map modules to files. These issues are either handled by the language itself
or delegated to external tools. Language-specific package managers have risen as a solution to these
problems, as they can perform module management portably and in a manner suited to the overall
design of the language. This paper presents LuaRocks, a package manager for Lua modules. LuaRocks
adopts a declarative approach for specifications using Lua itself as a description language and features
an extensible build system that copes with the heterogeneity of the Lua ecosystem.
47
ON THE PERFORMANCE OF MULTIDIMENSIONAL ARRAY REPRESENTATIONS IN
PROGRAMMING LANGUAGES BASED ON VIRTUAL EXECUTION MACHINES
Francisco Heron de Carvalho Junior (UFC), Cenez Araújo Rezende (UFC), Jefferson de Carvalho Silva
(UFC), Francisco José Lins Magalhães (UFC), and Renato Caminha Juaçaba-Neto (UFC)
This paper evaluates the performance of virtual execution machines (VM) of the CLI and JVM standards
for the common approaches to represent multidimensional arrays in high performance computing
applications. In particular, it shows which representation is the best for each virtual machine
implementation, showing that the choices may be surprisingly contradictory, even with respect to
previous results of other works on performance evaluation of VMs.
MODULAR BIALGEBRAIC SEMANTICS AND ALGEBRAIC LAWS
Ken Madlener (Radboud University Nijmegen), Sjaak Smetsers (Radboud University Nijmegen), and
Marko van Eekelen (Radboud University Nijmegen/Open University of the Netherlands)
The ability to independently describe operational rules is indispensable for a modular description
of programming languages. This paper introduces a format for open-ended rules and proves that
conservatively adding new rules results in well-behaved translations between the models of the
operational semantics. Silent transitions in our operational model are truly unobservable, which
enables one to prove the validity of algebraic laws between programs. We also show that algebraic
laws are preserved by extensions of the language and that they are substitutive. The work presented in
this paper is developed within the framework of bialgebraic semantics.
A DOUBLE EFFECT LAMBDA-CALCULUS FOR QUANTUM COMPUTATION
Juliana Kaizer Vizzotto (UFSM), Bruno Crestani Calegaro (UFSM), and Eduardo Kessler Piveta (UFSM)
In this paper we present a double effect version of the simply typed Lambda-calculus where we can
represent both pure and impure quantum computations. The double effect calculus comprises a
quantum arrow layer defined over a quantum monadic layer. In previous works we have developed
the quantum arrow calculus, a calculus where we can consider just impure (or mixed) quantum
computations. Technically, here we extend the quantum arrow calculus with a construct (and
equations)
that allows the communication of the monadic layer with the arrow layer of the calculus. That is, the
quantum arrow is defined over a monadic instance enabling to consider pure and impure quantum
computations in the same framework. As a practical contribution, the calculus allows to express
quantum algorithms including reversible operations over pure states and measurements in the middle
of
the computation using a traditional style of functional programming and reasoning. We also define
equations for algebraic reasoning of computations involving measurements.
48
BOILERPLATES FOR RECONFIGURABLE SYSTEMS: A LANGUAGE AND ITS SEMANTICS
Alexandre Madeira (Universidade do Minho/Universidade de Aveiro/Critical Software S.A), Manuel A.
Martins (Universidade de Aveiro), and Luís S. Barbosa (Universidade de Aveiro)
Boilerplates are simplified, normative English texts, intended to capture software requirements in a
controlled way. This paper proposes a pallet of boilerplates as a requirements modelling language for
reconfigurable systems, i.e., systems structured in different modes of execution among which they can
dynamically commute. The language semantics is given as an hybrid logic, in an institutional setting.
The mild use made of the theory of institutions, which, to a large extent, may be hidden from the
working software engineer, not only provides a rigorous and generic semantics, but also paves the way
to tool-supported validation.
CONTEXTUAL ABSTRACTION IN A TYPE SYSTEM FOR COMPONENT-BASED HIGH
PERFORMANCE COMPUTING PLATFORMS
Francisco Heron de Carvalho Junior (UFC), Cenez Araújo Rezende (UFC), Jefferson de Carvalho Silva
(UFC), and Wagner Guimarães Al-Alam (UFC)
This paper presents the formalization of HTS (Hash Type System), a type system for component-based
high performance computing (CBHPC) platforms. HTS aims at supporting an automated approach for
dynamic discovering, loading and binding of parallel components. HTS gives support for building
multiple implementations of abstract components, the performance of which are tuned according to
the specific features of high-end distributed-memory parallel computing platforms and the application
requirements, through context abstraction.
TOWARDS A DOMAIN-SPECIFIC LANGUAGE FOR PATTERNS-ORIENTED PARALLEL
PROGRAMMING
Dalvan Griebler (PUCRS), and Luiz Gustavo Fernandes (PUCRS)
Pattern-oriented programming has been used in parallel code development for many years now.
During this time, several tools (mainly frameworks and libraries) proposed the use of patterns based
on programming primitives or templates. The implementation of patterns using those tools usually
requires human expertise to correctly set up communication/synchronization among processes. In this
work, we propose the use of a Domain Specific Language to create pattern-oriented parallel programs
(DSL-POPP). This approach has the advantage of offering a higher programming abstraction level in
which communication/synchronization among processes is hidden from programmers. We compensate
the reduction in programming flexibility offering the possibility to use combined and/or nested parallel
patterns (i.e., parallelism in levels), allowing the design of more complex parallel applications. We
conclude this work presenting an experiment in which we develop a parallel application exploiting
combined and nested parallel patterns in order to demonstrate the main properties of DSL-POPP.
49
Multiple Intermediate Structure Deforestation by Shortcut Fusion
Alberto Pardo (Universidad de la República), João P. Fernandes (Universidade do Minho /Universidade
da Beira Interior), and João Saraiva (Universidade do Minho)
Shortcut fusion is a well-known optimization technique for functional programs. Its aim is to transform
multi-pass algorithms into single pass ones, achieving deforestation of the intermediate structures that
multi-pass algorithms need to construct. Shortcut fusion has already been extended in several ways.
It can be applied to monadic programs, maintaining the global effects, and also to obtain circular and
higher-order programs. The techniques proposed so far, however, only consider programs defined as
the composition of a single producer with a single consumer. In this paper, we analyse shortcut fusion
laws to deal with programs consisting of an arbitrary number of function compositions.
Zipper-based Attribute Grammars and their Extensions
Pedro Martins (Universidade do Minho), João P. Fernandes (Universidade do Minho / Universidade da
Beira Interior), and João Saraiva (Universidade do Minho)
Attribute grammars are a suitable formalism to express complex software language analysis and
manipulation algorithms, which rely on multiple traversals of the underlying syntax tree. Recently,
Attribute Grammars have been extended with mechanisms such as references and high-order
and circular attributes. Such extensions provide a powerful modular mechanism and allow the
specification of complex fix-point computations. This paper defines an elegant and simple, zipperbased embedding of attribute grammars and their extensions as first class citizens. In this setting,
language specifications are defined as a set of independent, off-the-shelf components that can easily
be composed into a powerful, executable language processor. Several real examples of language
specification and processing programs have been implemented in this setting.

SBLP - CBSoft 2013 - Universidade de Brasília

Transcrição

Documentos relacionados

Sabendo que 1 pé tem 30,48 cm e que 1 polegada tem 2,54 cm

Lista de exercícios 03

( MODELO DE PEDIDO DE DEMISSÃO) (para quem vai cumprir aviso)

Teste 1 (Ver. A)

Funç˜oes de Varias Variáveis - FVV - Noturno (2008) Profs. Stilante

interfaces R/C++ - wiki DPI

Prática

AV - Profmat

Bolo do Caco Bimby: 27 min Ingredientes: 1 c. café sal

FÁBRICA DE LEITE EM PÓ