Los programas al diván!
Programas que analizan programas
int insomnio(int dias) {
int tot=0; int i = 0;
while(i<dias) {
tot=tot+8;
i++;
}
return tot;
}
Diego Garbervetsky
Laboratorio Dependex
Aclaraciones
No soy Ingeniero de
Software!

No tengo moto…
Van a tener que ver
No mato
ratas
muchos
programitas!
No busco
petróleo
No juego con perritos
Analizando programas
Una mirada “psicológica”
void imprimir(int[] A) {
ordenar(A);
for(int i=0;i< a.length; i++) {
ordenar(A);
System.out.println(A[i]);
ordenar(A);
}
ordenar(A);
ordenar(A);
}
Neurótico
Obsesivo
Qué es el análisis de programas?
Técnicas para predecir propiedades de los
programas antes de ejecutarlos (o sea, saber de
antemano cosas que pasarán al ejecutarlos)
Algunas propiedades que interesan:
int noSoyOptimo(int n)

Variables “vivas”
{
x = n; {n}
acum = n; {acum}
i = 0; {acum, i}
while(i< 10) {acum, i}
{
k = i + 1; {acum, k}
acum = acum + 1; {acum, k}
i = k; {acum, i}
}
return acum; { acum }
• Una variable está viva en una posición
del programa si es USADA en alguna
posición a partir de ese punto SIN SER
REASIGNADA
• Una variable ASIGANDA pero no viva,
puede ser eliminada junto con sus
ASIGNACIONES
}
Qué es el análisis de programas?
Técnicas para predecir propiedades de los
programas antes de ejecutarlos (o sea, saber de
antemano cosas que pasarán al ejecutarlos)
Algunas propiedades que interesan:


Variables “vivas”
int noSoyOptimo(int n, int[] a)
Expresiones usadas frecuentemente
{
• Una expresión es usada frecuentemente si
aparece varias veces en un programa y el
valor que representa es siempre el mismo.
acum = 0;
for(int i=0; i< 10; i++)
{
a[2*n+i]=a[2*n+i]+1;
acum = acum + a[2*n+i];
}
return m;
}
Qué es el análisis de programas?
Técnicas para predecir propiedades de los
programas antes de ejecutarlos (o sea, saber de
antemano cosas que pasarán al ejecutarlos)
int noSoyOptimo(int n)
Algunas propiedades que interesan:
{
{ true }
Variables “vivas”
acum = n;
 Expresiones usadas frecuentemente
{ acum = n }
for(int i=0; i< 10; i++) {
 Invariantes
{0≤ i<10  acum=n+i }
 Accesos
correctos
(punteros)
Invariante
en un
punto: a Arrays, a referencias
acum = acum + 1;
Relación
entre
variables que se
 Código
alcanzable
{0≤ i<10  acum=n+i+1 }
}
mantiene
para
 Tiempo
decualquier
ejecución
{ i = 10  acum=n+10 }
ejecución
de
un
programa
 Y muchas más!
return acum;

}
Tipos de Análisis
Dos enfoques

Estático: Se analiza el programa sin
ejecutarlo.
Se deduce el comportamiento a partir del
TEXTO del código.

Dinámico: Se ejecuta el programa
(varias veces)
Se deduce el comportamiento a partir de
datos obtenidos de las ejecuciones.
El TESTING es un tipo análisis dinámico
Vamos a hablar de Análisis Estático
Motivación
Por qué analizar programas?
Generación de Código



Compilación
Optimización
Transformación
Verificación



Contra especificaciones
Bugs en código
Generación de casos de Test
Comprensión


Obtención de invariantes
Obtención de modelos a partir de código
Seguridad

Buffer overflows…
Por qué analizar programas?
Generación de Código
Compilar: Transformar un programa en un
lenguaje que nosotros “entendemos” por
algo que entiende la máquina
int ordenar(int[] A)
{
for(int i=0;i< a.size; i++)
{
swap(i, min(A,i) );
}
}
ordenar
Mov cx,0
L1: call minimo
Mov bx, data[ax]
Mov ex, data[cx]
Mov data[cx], bx
Mov data[ax], ex
Inc cx;
cmp cx,data[size]
jnz L1
Estructura de un Compilador
Código=Texto
Cadena
de Tokens
Analizador
Léxico
Parser
Optimizador
especifico
para el procesador
Código
optimizado
para una
máquina
específica
Representación
Intermedia
Síntaxis
Abstracta
Código para
una máquina
especifica
Analizador
Semántico
Generador
de código
Optimizador
independiente
del procesador
Representación
Intermedia
Optimizada
Por qué analizar programas?
Optimizar
Optimizar: Hacer algo más eficiente según
algún criterio…
Espacio!
Miss Gorda 2004 - Foto: Terra/Reuters
Pampita - Foto: HardDisk E. Mockscos
Por qué analizar programas?
Optimizar
Optimizar: Hacer algo más eficiente según
algún criterio
int noSoyOptimo(int x)
{
int n = x;
int h = 10;
int m;
for(int i=0; i< 1000; i++)
{
m = max(n,h);
}
return m;
}
int soyOptimo(int x)
{
return max(x,10);
}
•Espacio!
•N° de instrucciones ejecutadas!
•Velocidad!
Optimizaciones Típicas
Evitar cómputos redundantes


Reusar resultados disponibles
Sacar de los “loops” los resultados que no
varían en ellos
Evitar cómputos superfluos


Resultados no necesarios
Resultados calculables en tiempo de
compilación (ej.:constantes)
Reusar resultados disponibles
int noSoyOptimo(int n, int[] a)
{
acum = 0;
Primer cálculo
for(int i=0; i< 10; i++)
{
a[2*n+i]=a[2*n+i]+1;
acum = acum + a[2*n+i];
}
return m;
}
Cálculos repetidos
int soyMasOptimo(int n, int[] a)
{
acum = 0;
for(int i=0; i< 10; i++)
{
tmp = 2*n+i;
a[tmp]=a[tmp]+1;
acum = acum + a[tmp];
}
return m;
}
Otros análisis
Instrucciones que no dependen
del loop
int noSoyOptimo(int x)
{
int n = x;
int h = 10;
int m;
for(int i=0; i<1000; i++)
{
m = max(n,h);
}
return m;
}
Resultados calculables en
tiempo de compilaciòn
Resultados no necesarios
int noSoyOptimo(int x)
{
int n = x; { x }
x) int h = 10; { x }
int m; {x}
m = max(x,10); {m}
return m; {}
}
n, h no están
m;
vivas!!
h es constante
int noSoyOptimo(int x)
{
int n = x;
intintcasiOptimo(int
h = 10;
{ int m;
m = max(n,h);
int
m;
return m;
} m = max(x,10);
return
}
No depende del Loop
n es siempre x
Analizando programas
Una mirada “psicológica”
Esquizofrénico!
void imprimir(int[] A)
{
System.out.println(A[i]);
i=i-i;
while(a.length<i);
i = 0;
}
Por qué analizar programas?
Verificar
Dos enfoques

1) Ver si el programa cumple con lo
especificado.
Testing… (dinámico)
Descubrir invariantes y comparar (estática o
dinámicamente)

2) Evitar la mayor cantidad errores en tiempo
de ejecución
chequeo de accesos indebidos a arrays,

A[i] con i mayor a la dimensión del array o negativo!
punteros nulos,
variables no inicializadas…
WARNING!
Ingeniería
de Software
Verificación Ejemplos
WARNING!
Ingeniería
de Software
PolySpace aplica técnicas análisis
estático para la verificación de
programas “críticos”
Verificó una aplicación de
sincronización de los trenes de alta
POTENCIALES
velocidad
TGV (Francia) ERRORES EN
15.000 EJECUCION!
líneas de código
Descubrió (sin ejecutar) los
!!!!!CHOQUES!!!!!!
siguientes
tipos de errores:




Acceso a variables no inicializadas
Divisiones por zero
Acceso fuera de límites de Arrays
Acceso concurrente a variables
compartidas sin sincronizar
Limites del Análisis
El problema de la Parada…
Sea “Tusam” un programa que dado otro
programa nos dice si este para o no.
SI
si P para
NO
si P se “cuelga”
Tusam(P) =
Existe el programa Tusam?
Limites del Análisis
Supongamos que existe Tusam
Sea “TonyKamo” otro programa
Se cuelga si Tusam(P) = SI
TonyKamo(P) =
OK
si Tusam(P) = NO
Absurdo!
Que pasa si corremos TonyKamo(TonyKamo)?
1) Si se cuelga, entonces Tusam(TonyKamo)=SI, entonces
Tonykamo para!, pero se colgó…
2) Si da OK, entonces Tusam(TonyKamo) =NO, entonces
TonyKamo se cuelga, pero dio OK!
Consecuencias
El problema de la parada no es computable
Lamentablemente muchos problemas tampoco
lo son. Ejemplos:



Decidir si un punto del programa es alcanzable por
alguna ejecución o no (código muerto)
Calcular (exactamente) cuanta memoria necesita un
programa para ejecutarse
Saber si dos variables refieren al mismo objeto
(aliasing)
Aproximaciones
No dar el resultado exacto (ya vimos que a veces es
imposible)
Dar una aproximación conservativa


Tener en cuenta para que vamos a usar el resultado del análisis
Tiene que ofrecer datos SEGUROS según la transformación
que hagamos
Copiar Constantes
Variables Vivas
= Espacio de soluciones exacto
= Espacio aproximado
Analizando programas
Una mirada “psicológica”
Narcisista…
void imprimir(int[] A)
{
for(int i=0;i< A.length; i++) {
System.out.println("Soy groso!“
+A[i]);
}
}
Que estamos haciendo?
Nos interesan los programas que
corren en “aparatitos” (sistemas
embebidos)


Limitaciones de espacio y poder de
computo
Aplicaciones “generalmente” críticas
También nos interesan los
sistemas de tiempo real
 Necesitamos predictibilidad
temporal (saber que cierto proceso
SIEMPRE tarda menos que X
tiempo)
Problemas en sistemas embebidos
Son generalmente críticos y de tiempo
real
Usan lenguajes de programación de bajo
nivel


Difíciles de programar y propensos a errores
Muy difíciles de verificar
Es un quilombo!
Tenemos que buscar formas de trabajar
con lenguajes más modernos y
“cómodos”.
Programador de
embebidos
www.Soypelado.com.ar
Análisis de Memoria en lenguajes
orientados a Objetos
Los lenguajes orientados a objetos tienen
muchas ventajas:


Abstracción, encapsulación, Modularidad, Reuso, etc.
Muchos programadores y diseñadores “conocen”
POO •No son predecibles!!
Casi no usados
sistemas
críticos o de
•Muy para
difícil
analizarlos!!!
tiempo real...
Problemitas:


Garbage Collector (recolección de objetos ya no
utilizados)
Binding dinámico y polimorfismo
Modelo de Memoria en Lenguajes
Modernos
void usoMemoria(int n)
{
Carita v;
for(int i=0;i<n;i++)
{
v = dameObjeto();
System.out.print(v);
}
}
Carita dameObjeto()
{
Carita ret = new Carita()
return ret;
}
v
Modelo de Memoria en Lenguajes
Modernos
void usoMemoria(int n)
{
Carita v;
for(int i=0;i<n;i++)
{
v = dameObjeto();
System.out.print(v);
}
}
Carita dameObjeto()
{
Carita ret = new Carita()
return ret;
}
v
Señor
Garbage
Collector
Problema
No sabemos cuando actua el GC
No sabemos cuanto va a tardar
El GC es Malo… (para nosotros!)
Tenemos que eliminarlo!!!!
SOY MALO!!!
Modelo de Memoria en Lenguajes OO
Nosotros podemos darnos cuenta
que los objetos dejan de estar
“Apuntados”
Analizando el Código!
v
Entonces podemos modificar
el código para hacer lo mismo
que el Garbage Collector…
Cuando y de la forma que querramos!
El programador NI SE ENTERA!
Más cosas sobre la memoria
Recordemos que nos interesa la predictibilidad
y que tenemos poco espacio (aparatitos!)
Nos interesa mucho administrar bien la memoria
Necesitamos:


Entender como trabajan los programas con la
memoria (tiempo de vida de los objetos que
alocamos)
Administrar bien la memoria
Mecanismo eficiente y predictivo sin el GC!

Poder aproximar el consumo!!
Más cosas…
Análisis de Invariantes
Invariante: Relación entre variables que
debe cumplirse siempre
Nos explican que pasa con el programa
en determinados puntos
Sirven para entender
Para verificar
Y para estimar consumo de memoria!
Análisis de Invariantes Estático
{ no se nada…}
int maximoPrieto(int x, int y)
{
1: int ret = 1:
ret =1
{ ret = 1 }
2: if(x!=1)
3:
4:
{
x != 1
if(x>y)
ret = x;
else
5:
ret = y;
}
{ ret = 1  x!=1 }
x>y
{ ret = 1  x!=1  x > y }
{ ret = 1  x!=1  x ≤ y }
ret =x
ret = y
{ ret = x  x!=1  x > y }
{ ret = y  x!=1  x ≤ y }
return ret
6: return ret;
}
{ ret = 1  x= 1 }
{
(x!=1  ((x > y  ret = x)  (x ≤ y  ret = y)) )
 (x = 1  ret = 1) }
Análisis Invariantes Dinámico
int maximoPrieto(int x, int y)
{
1: int ret = 1:
2: if(x!=1)
3:
4:
{
if(x>y)
ret = x;
else
5:
ret = y;
}
Se deduce un valor según las trazas de
ejecución
1: (ret=1, x=3, y=4)
2: (ret=1, x=3, y=4)
3: (ret=1, x=3, y=4)
5: (ret=4, x=3, y=4)
6: (ret=4, x=3, y=4)
1: (ret=1, x=6, y=4)
2: (ret=1, x=6, y=4)
3: (ret=1, x=6, y=4)
4: (ret=6, x=6, y=4)
6: (ret=6, x=6, y=4)
1: (ret=1, x=4, y=4)
2: (ret=1, x=4, y=4)
3: (ret=1, x=4, y=4)
5: (ret=4, x=4, y=4)
6: (ret=4, x=4, y=4)
1: (ret=1, x=5, y=4)
2: (ret=1, x=5, y=4)
3: (ret=1, x=5, y=4)
4: (ret=5, x=5, y=4)
6: (ret=5, x=5, y=4)
6: return ret;
Se deduce que en 6: ret = Maximo(x,y)
}
Y si nunca ejecutamos con x=1??
Otras cosas: Analisis de consumo de
memoria en Java
Dado un método (función o procedimiento)
obtenemos un polinomio en función de sus
parámetros que sobre aproxima la cantidad de
memoria que necesita para correr
void usoMemoria(int n)
{
for(int i=0;i<n;i++) {
for(int j=0;j<i;j++) {
C v = new C();
}
}
}
Inv ={ 0≤i<n  0≤j<i }
P(n) = ½ n2 + ½n
Mago
Capria
DePendex - Laboratorio de investigación
en Software Confiable
Alfred Olivero
Si, Victor es Groso!
Chapa
Andran “Guru” Eclipse
Nico
Sergio Yovine
Yo
Diego “Invariante” Piemonte
Que hacemos en DEPENDEX?
Modelado y análisis de sistemas de tiempo real



Lenguajes gráficos para describir requerimientos
temporales
Model Checking
Extracción de modelos a partir de diseños
Predicción de uso de memoria



Análisis de “tiempo de vida” de los objetos
Transformación de código
Calculo de Invariantes
Programación orientada a Aspectos
Dependex – Proyectos / Aplicaciones
Modelado, análisis y verificación de Sistemas de
Tiempo Real

VInTime: Un tool-suite para la verificación de sistemas de
tiempo real
Lapsus: Herramienta para diseño de sistemas de tiempo real
VTS: Un lenguaje grafico para la especificación de requerimientos
ObsSlice: Un reductor “exacto” de sistemas de tiempo real
Zeus: Un “model checker” distribuido basado en KRONOS.

TraceIt!: Generador de trazas de eventos para sistemas de
tiempo real distribuidos
Herramientas que operan sobre programas




JScoper: Un plug-in para Eclipse que facilita la traducción de
aplicaciones Java estándar a Java Real Time
JMemory: Un estimador simbólico del consumo de memoria de
aplicaciones java
JInvariant: Un generador automático de invariantes poliédricos
para programas Java
SetPoint: Una heramienta para Programación Orientada a
Aspectos basada en poincuts semánticos
FIN!
PREGUNTAS?
Quedo
algo de
vino?