Detectando No-Sleep Energy Bugs

Prévia do material em texto

UNICAMP, Instituto de Computação
Implementação de Linguagens II: Detectando
No-Sleep Energy Bugs
Prof. Edson Borin
31 de maio de 2017
Introdução
Os últimos anos foram marcados por uma drástica mudança no mercado de computado-
res: o declínio da venda de "desktops"e o crescimento na venda de dispositivos móveis,
em especial smartphones. Consequentemente, como os primeiros são ligados diretamente
a tomada mas os segundos dependem de bateria, tivemos, também, um aumento na
dependência em eficiência energética. Por isso, os sistemas operacionais (SO) desses
dispositivos móveis, diferente dos para computadores pessoais, aplicam técnicas de eco-
nomia e gerenciamento de energia muito mais agressivas, como por exemplo: desativar
ou colocar em modo idle qualquer parte do aparelho que não esteja em uso por uma
pequena quantidade de tempo. Note que os dispositivos móveis possuem uma maior va-
riedade de periféricos, como GPS, giroscópio, etc; que nem sempre estão sendo utilizados,
justificando, assim, o desligamento frequente e agressivo dos mesmos.
Como resultado disso, uma aplicação tem dificuldade em utilizar continuamente um
periférico como o GPS, porque o SO desliga-o na menor espera da aplicação. Imagine que
o app tenha que esperar uma resposta http de um servidor. Essa espera pode resultar
na inatividade do GPS, fazendo com que o SO desligue-o. Para contornar esse problema,
foram adicionados na API do SO wakelockers que bloqueiam o uso de um periférico,
sendo, agora, de responsabilidade do programar bloquear e desbloquear o uso de um
periférico, mantendo-o ligado.
Da mesma forma que com lockers na programação paralela, erros na implementação
podem levar ao bloqueio de um dispositivo sem que ele seja desbloqueado futuramente,
causando um excessivo uso de energia. Pathak et al. [3] descrevem esses bugs de energia,
1
os no-sleep energy bugs, e os categorizam de três formas: no-sleep code path, no-sleep race
condition e no-sleep dilatation.
Nesse trabalho iremos desenvolver um sistema automatizado para detecção de no-sleep
code path, ou seja, encontrar caminhos no fluxo de execução (CFG) do programa afim de
encontrar um que possua a captura de um wakelock, mas não sua liberação. Para isso,
você deverá implementar uma análise próxima ao reaching definition [1], como a descrita
por Pathak et al.
O Trabalho
Serão fornecidas diversas aplicações no formato de bitcode LLVM 4.0 [2] contendo inúme-
ras chamadas as funções void getWakeLock(int) e void freeWakeLock(int). Essas
funções podem travar ou liberar o uso de periféricos do dispositivo, onde o periférico é
especificado pelo número (int) passado como parâmetro.
Você deverá (1) criar um passo LLVM que emita na saída padrão de erro (stderr)
uma versão simplificada do CFG da aplicação, contendo apenas nomes das funções, blocos
básicos, arestas e chamadas a funções; Além disso, terá que (2) criar um outro passo
LLVM que instrumente a aplicação para que em sua execução seja emitido no stderr
todos as chamadas distintas (próximo a um call graph dinâmico). Por último, você terá
que (3) implementar a análise descrita por Pathak et al. sobre o CFG simplificado
emitido pelo passo (1) e com as informações dinâmicas da aplicação obtidas pelo passo
(2). No final da execução, duas saídas serão esperadas: se possui ou não um no-sleep code
path bug e o caminho do CFG que gera esse bug. O trabalho se resume ao fluxograma
da Figura 0.1.
1) Passo LLVM: emissão 
do CFG simplificado
Bitcode LLVM 4.0 2) Passo LLVM: 
instrumentação do App
Bitcode LLVM 4.0
Info. Dinâmica 
dos calls
Execução do App. 
instrumentado
CFG 
Simplicado
3) Detector de no-sleep 
code path bugs
Sim/Não Bug Path
Figura 0.1: Fluxograma da aplicação desenvolvida no trabalho.
2
Observações importantes:
• Deverá ser utilizado o LLVM 4.0.
• As saídas deverão seguir o padrão descrito na seção seguinte.
• Os passos LLVM poderão ser desenvolvidos em C ou C++.
• O detector de no-sleep code path bugs poderá ser desenvolvido em qualquer lingua-
gem.
Padrão da Saída Esperada
CFG Simplificado (saída do passo 1):
Essa saída representa um CFG para cada função definida no bitcode, seguindo o seguinte
padrão: primeira linha deverá conter o número "f" de funções; para cada função, uma
linha com o nome da função seguido do número "n" de blocos básicos do seu CFG e do
número "e" de arestas do seu CFG; para cada bloco básico, o número "id" de identifi-
cação do bloco seguido da quantidade "c" de calls; cada call será identificado pela linha
"l", coluna "c" no código fonte, de uma flag ‘c’ ou ‘i’ dependendo se a chamada é direta
ou indireta, todos separados por ‘:’ e, caso seja direta, também conterá o nome. Por fim,
as arestas são representadas por "‘id’ -> ‘id’".
Obs.: O primeiro bloco básico (id 1) de cada função deverá ser o bloco de entrada e todos
os blocos que não possuírem arestas saindo deles serão considerados blocos de saída.
Resumo da sintaxe:
f
nomeFuncao n e
id c
l:c:flag:nomeFuncao
id -> id
...
Exemplo:
2
Z5rand2v 1 0
1 1
8:3:c:printf
Z5maainiPPc 4 4
1 0
11:15:i
11:28:i
12:10:i
2 0
3 0
3
4 0
18:3:i
1 -> 2
1 -> 3
2 -> 4
3 -> 4
Info. Dinâmica dos Calls (saída do passo 2):
Um call por linha, não podendo se repetir. Cada call poderá gerar duas informações:
source e target que serão denotadas pelas flags "s"ou "t", respectivamente. O source
terá a linha e coluna do call e o target o nome da função chamada.
Obs.: note que uma chamada sempre possuí um source, mas não necessariamente um
target, já que nem sempre temos informações de todas as funções antes de linkarmos.
Exemplo:
s 18:3
t Z5rand2v
s 8:3
Saída do detector de bugs (saída do passo 3):
A saída do detector deverá começar com sim ou não, indicando se há ou não bugs. Caso
comece com sim, deverá ser seguido do número de bugs. Para cada, terá a palavra bug e
a posição (linha e coluna) da chamada do getWakeLock que gerou esse bug, seguido do
menor caminho da saída até esse get. Em caso de empates no tamanho dos caminhos,
qualquer um entre os menores poderá ser usado como resposta. O caminho será formado
pelos nomes das funções e ids dos blocos básicos do CFG.
Exemplo:
sim
2
bug 18:3
Z5maainiPPc
1 -> 2
2 -> 4
bug 5:8
main 1 -> 3
Avaliação
Um conjunto de aplicações será disponibilizado junto a esse trabalho, mas um outro
conjunto maior será utilizado para avaliação. Sua nota será diretamente proporcional a
quantidade de bugs identificados, assim, se identificar todos os bugs em todos os testes,
receberá 100% da nota.
4
Importante: Com apenas o primeiro passo e o analisador (sem as informações di-
nâmicas dos calls) será possível detectar 80% dos bugs, ou seja, essa parte do trabalho
valerá 80% da nota.
Referências
[1] Alfred V Aho, Monica S Lam, Ravi Sethi, and Jeffrey D Ullman. Compilers, Princi-
ples, Techniques. Addison wesley Boston, 2007.
[2] Chris Lattner and Vikram Adve. LLVM: A Compilation Framework for Lifelong
Program Analysis & Transformation. In Proceedings of the 2004 International Sym-
posium on Code Generation and Optimization (CGO’04), Palo Alto, California, Mar
2004.
[3] Abhinav Pathak, Abhilash Jindal, Y Charlie Hu, and Samuel P Midkiff. What is
keeping my phone awake?: characterizing and detecting no-sleep energy bugs in
smartphone apps. In Proceedings of the 10th international conference on Mobile
systems, applications, and services, pages 267–280. ACM, 2012.
5