Introdução A linguagem de programação

Prévia do material em texto

Linguagens
de
Programação

Fernando
Magno
Quintão
Pereira

•  O
que
são
linguagens
de
programação?

•  Por
que
elas
existem?

•  Como
computadores
eram
programados
antes

das
linguagens
de
programação?

A
Torre
de
Babel

•  Existem
entre
5.000
e
6.000

línguas
faladas
em
nosso

planeta.

•  Cerca
de
200
idiomas

possuem
mais
de
um
milhão

de
falantes.

•  Como
descrever
um
idioma?

Que
elementos
estão

presentes
na
descrição
de

uma
linguagem?

Computadores
também
conversam

•  Como
é
a
linguagem

falada
pelos

computadores?

– Que
símbolos
ela
usa?

– Quais
palavras?

– Como
seria
a
gramáMca

dessa
língua
eletrônica?

Vamos
falar
zero‐um‐nês?

•  Computadores
possuem

cordas
vocais
muito
simples:

ou
emitem
som,
ou
não

emitem

•  É
possível
haver
uma

linguagem
com
apenas
dois

símbolos?

•  Porque
somente
dois

símbolos?

Dialetos
do
zero‐um‐nês

•  Há
muitas
linguagens
de

zeros
e
uns
diferentes,
assim

como
há
muitas
linguagens

diferentes
usando

caracteres
laMnos:
inglês,

português,
espanhol,
etc.

•  Quem
me
dá
exemplos
de

zero‐um‐nês
diferentes?

“The
book
is
on
the
table”

•  Cada
instrução
em
zero‐um‐nês
possui
um

nome,
chamado
opcode,
e
operandos.

•  Instruções
mudam
o
estado
do
computador.

•  Que
Mpos
de
instruções
poderiam
exisMr?

•  Falar
zero‐um‐nês
deve
ser
fácil,
não
é?

Mas
não
é
não…

•  AnMgamente
programar

computadores
era
muito

di[cil.

•  Qual
o
problema
com
zero‐
um‐nês?

•  Alguém
ai
conhece
cartões

perfurados?

•  Como
deixar
zero‐um‐nês

mais
fácil
de
usar?

E
veio
a
Deusa

•  Palavras
são
mais
fáceis

de
lembrar
que

sequências
de
zeros
e

uns.

•  Por
exemplo:
qual

instrução
é
mais
fácil
de

ler:
mov $1, AL,

ou

10110000 
01100001?

O
que
este
programa
faz?

 movl $5, %eax 
 movl $1, %edx 
.L4: 
 imull %eax, %edx 
 decl %eax 
 testl %eax, $0 
 jg .L4 
O
que
este
programa
faz?

 movl $5, %eax 
 movl $1, %edx 
.L4: 
 imull %eax, %edx 
 decl %eax 
 testl %eax, $0 
 jg .L4 
Coloque
5
em
eax

Coloque
1
em
edx

MulMplique
eax
por
edx
e

coloque
o
resultado
em
edx

Subtraia
1
de
eax

Teste
se
eax
é
0

não

O
Montador

•  As
pessoas
falavam

assembly,
mas
os

computadores
ainda

falavam
zero‐um‐nês.

– Era
preciso
um
tradutor.

•  O
que
um
tradutor

deste
Mpo
deveria
ser

capaz
de
fazer?

A
Deusa
não
foi
suficiente

•  Programar
em
assembly
ainda
era
di[cil.

•  Os
programadores
queriam
que
os

computadores
fossem
capazes
de
falar
línguas

ainda
mais
parecidas
com
linguagens

humanas.

•  Quais
foram
as
primeiras
linguagens
de

programação?

•  Quem
foram
os
pais
dessas
linguagens?


Surge
Fortran

•  John
Backus
estava
com

preguiça
de
escrever

programas
em
assembly.

•  IBM
1953/54

•  Programar
ficou
umas
20

vezes
mais
fácil

– Mas
as
pessoas
ainda

estavam
relutantes…

Porque?

Exemplo
de
programa
em
Fortran

nfact=1 
do i=1, 5 
 nfact = nfact*I 
enddo 
 movl $5, %eax 
 movl $1, %edx 
.L4: 
 imull %eax, %edx 
 decl %eax 
 testl %eax, $0 
 jg .L4 
Fortran
 Assembly

Que
novidades
surgiram

com
Fortran?

E
Surge
LISP

•  1958,
Massachuse=s
Ins?tute
of
Technology

•  Professor
John
McCarthy.

•  Uma
notação
simples,
baseada
em
funções

matemáMcas.

•  Muitos
parênteses,

•  E
listas…

Exemplo
de
Programa
em
LISP

(defun factorial (n) 
 (if (<= n 1) 
 1 
 (* n (factorial (- n 1))))) 
nfact=1 
do i=1, n 
 nfact = nfact*I 
enddo 
Fortran

LISP

E
quando,
nos
anos
70,

os
soviéMcos
conseguiram

as
úlMmas
500
linhas
do

sistema
de
mísseis

americanos…

Recursão!

ALGOL
–
um
Mme
de
estrelas

•  Precisava‐se
de
um
padrão
para

algoritmos.

•  Um
comitê
foi
formado
em
1958.

–  John
Backus

– C.
A.
R.
Hoare

–  John
McCarthy,
etc

•  Desse
comitê
nasceu
ALGOL
58.

•  Talvez
a
mais
influente

linguagem
de
programação.

ALGOL
–
exemplo

integer
procedure
Factorial(m);

integer
m;

Begin









integer
F;










F
:=
if
m=1
then
1
else
m*Factorial(m‐1);









Factorial
:=
F

end;

•  Vocês
já
viram
algo
parecido
com
isto?

E
COBOL

•  COBOL
foi
feita
para
negócios:

– Contadores,
economistas,
etc

– Como
deveria
ser
uma

linguagem
assim?

•  1958:
COBOL
foi
criada
por

um
comitê.

–  Indústria,
governo
e
academia

•  Ainda
usada
em
muitas

companhias,
até
em
BH!

Exemplo
de
programas
em
COBOL

ADD YEARS TO AGE. 
MULTIPLY PRICE BY QUANTITY GIVING 
COST. 
SUBTRACT DISCOUNT FROM COST GIVING 
FINAL-COST. 
•  Quantas
linguagens
de
programação
existem?

•  Quais
as
linguagens
mais
populares?

Quantas
são?

•  A
editora
O’Reilly
diz
que

existem
2.500
linguagens

de
programação

documentadas.

•  A
wikipédia
documenta

650.

•  Existem
muitas…

•  Mas,
porque
tantas?

Propósitos
diferentes

•  Fortran
servia
para
cálculos

cienwficos.

•  Lisp
era
usada
em
teoria
da

computação.

•  COBOL
foi
feita
para
aplicações

comerciais.

•  Algol
é
uma
linguagem

acadêmica.

•  E
as
outras
linguagens
que

conhecemos?

Quais
são
as
linguagens
pop?

•  Dados
reMrados
de

www.tiobe.com 
–  Java:
18.71%

– C:
16.89%

– PHP:
10.39%

•  Google
code:
C,
Java,
C++,

PHP

•  Craigslist:
PHP,
C,
SQL

•  Que
outras
medidas?

Alguém
aí
fala
Javanês?

•  De
acordo
com
muitos
critérios,
Java
é
a
a

linguagem
mais
popular.

•  Para
que
serve
Java?

•  Como
essa
linguagem
surgiu?

•  O
que
ela
tem
de
mais?

Um
exemplo
de
javanês:

public class Fact { 
 public static void main(String a[]) { 
 int n = 5; 
 int fact = 1; 
 while (n > 1) { 
 fact *= n; 
 n--; 
 } 
 System.out.println(fact); 
 } 
} 
é
A,
é
B,
é
C…

•  C
surgiu
em
1972,
e
foi,
durante
muitos

anos,
a
linguagem
de
programação
mais

popular.

•  Porque
C
tem
este
nome?

•  O
que
a
gente
faz
com
C?

•  Porque
C
foi
tão
popular?

•  Quais
os
problemas
com
C?

•  C
teve
grande
influência…

Falando
em
C…

int main() { 
 int n = 5; 
 int fact = 1; 
 while (n > 1) { 
 fact *= n; 
 n--; 
 } 
 printf("%d\n", fact); 
} 
•  Alguém
já
viu
isto
antes?

C
teve
grande
influência…

int n = 5; 
int fact = 1; 
while (n > 1) { 
 fact *= n; 
 n--; 
} 
int n = 5; 
int fact = 1; 
while (n > 1) { 
 fact *= n; 
 n--; 
} 
Figure 1. Web application architecture.
effectively under a heavy load of requests. Finally, some runtime
techniques [23, 24] require a modified runtime system, which con-
stitutes a practical limitation in terms of deployment and upgrading.
Static analyses to find SQLCIVs have also been proposed, but
none of them runs without user intervention and can guarantee the
absence of SQLCIVs. String analysis-based techniques [3, 20] use
formal languages to characterize conservatively the set of values a
string variable may assume at runtime. They do not track the source
of string values, so they require a specification, in the form of a
regular expression, for each query-generating point or hotspot in
the program — a tedious and error-prone task that few program-
mers are willing to do. Static taint analyses [12, 18, 31] track the
flow of tainted (i.e., untrusted) values through a program and re-
quire that no tainted values flow into hotspots. Because they use
a binary classification for data (tainted or untainted), they classify
functions as either being santitizers (i.e., all return values are un-
tainted) or being security irrelevant. Because the policy that these
techniques check is context-agnostic, it cannot guarantee the ab-
sence of SQLCIVs without being overly conservative. For exam-
ple, if the escape quotes function (which precedes quotes withan “escaping” character so that they will be interpreted as charac-
ter literals and not as string delimiters) is considered a sanitizer, an
SQLCIV exists but would not be found in an application that con-
structs a query using escaped input to supply an expected numeric
value, which need not be delimited by quotes. Additionally, static
taint analyses for PHP typically require user assistance to resolve
dynamic includes (a construct in which the name of the included
file is generated dynamically).
1.2 Our Approach
We propose a sound, automated static analysis algorithm to over-
come the limitations described above. It is grammar-based; we
model string values as context free grammars (CFGs) and string
operations as language transducers following Minamide [20]. This
string analysis-based approach tracks the effects of string opera-
tions and retains the structure of the values that flow into hotspots
(i.e., where query construction occurs). If all of each string in the
language of a nonterminal comes from a source that can be influ-
enced by a user, we label the nonterminal with one of two labels.
We assign a “direct” label if a user can influence the source di-
rectly (as with GET parameters) and a “indirect” label if a user can
influence the source indirectly (as with data returned by a database
query). Such labeling tracks the source of string values. We use
a syntax-based definition of SQL injection attacks [25], which re-
quires that input from a user be syntactically isolated within a gen-
erated query. This policy does not need user-provided specifica-
tions. Finally, we check policy conformance by first abstracting the
labeled subgrammars out of the generated CFG to find their con-
texts. We then use regular language containment and context free
language derivability [28], to check that each subgrammar derives
only syntactically isolated expressions.
We have implemented this analysis for PHP, and applied it to
several real-world web applications. Our tool scales to large code
bases — it successfully analyzes the largest PHP web application
...
01 isset ($ GET['userid']) ?
02 $userid = $ GET['userid'] : $userid = '';
03 if ($USER['groupid'] != 1)
04 {
05 // permission denied
06 unp msg($gp permserror);
07 exit;
08 }
09 if ($userid == '')
10 {
11 unp msg($gp invalidrequest);
12 exit;
13 }
14 if (!eregi('[0-9]+', $userid))
15 {
16 unp msg('You entered an invalid user ID.');
17 exit;
18 }
19 $getuser = $DB->query("SELECT * FROM `unp user`"
20 ."WHERE userid='$userid'");
21 if (!$DB->is single row($getuser))
22 {
23 unp msg('You entered an invalid user ID.');
24 exit;
25 }
...
Figure 2. Example code with an SQLCIV.
previously analyzed in the literature (about 100K loc). It discovered
many vulnerabilities, some previously unknown and some based on
insufficient filtering, and generated few false positives.
2. Overview
In order to motivate our analysis, we first present the policy that
defines SQLCIVs, and then give an overview of how our analysis
checks web applications against that policy.
2.1 SQL Command Injection Vulnerabilities
This section illustrates SQLCIVs and formally defines them.
2.1.1 Example Vulnerability
Figure 2 shows a code fragment excerpted from Utopia News Pro,
a real-world news management system written in PHP; we will
use this code to illustrate the key points of our algorithm. This
code authenticates users to perform sensitive operations, such as
managing user accounts and editing news sources. Initially, the
variable $userid gets assigned data from a GET parameter, which
a user can easily set to arbitrary values. The code then performs two
checks on the value of $userid before incorporating it into an SQL
query. The query should return a single row for a legitimate user,
and no rows otherwise. From line 14 it is clear that the programmer
intends $userid to be numeric, and from line 20 it is clear that
the programmer intends that $userid evaluate to a single value
in the SQL query for comparison to the userid column. However,
because the regular expression on line14 lacks anchors (‘^’ and ‘$’
for the beginning and end of the string, respectively), any value for
$userid that has at least one numeric character will be included
into the generated query. If a user sets the GET parameter to “1';
DROP TABLE unp user; --”, this code will send to the database
the folloing query:
SELECT * FROM `unp user` WHERE userid='1';
DROP TABLE unp user; --'
A
Internet
respira
PHP

•  Alguém
aqui
já
programou
em
PHP?

•  O
que
esse
nome
quer
dizer?

•  Como
deve
ser
uma
linguagem
para

desenvolvimento
web?

Um
exemplo
de
PHPês:

$id = $_GET[”user”]; 
if ($id == '') { 
 echo "Invalid user: $id" 
} else { 
 $getuser = $DB->query 
 (”SELECT * FROM 'table' WHERE id=’$id’”); 
 echo $getuser; 
} 
•  Alguém
notou
um
pouquinho
de
C
aí?

•  Qual
o
Mpo
da
variável
$id?

•  Computadores
falam
zero‐um‐nês,
nós

falamos
linguagens
de
programação…
quem

traduz
estas
coisas?

•  E
como
essa
tradução
é
feita?

Compiladores
são
pontes

•  O
primeiro
compilador
foi,

provavelmente,
o
A-0
de

Grace
Hopper
(1949).

•  Linguagens
de

programação
diferentes

possuem
diferentes

compiladores.

•  Mas
o
mesmo
compilador

também
pode
compilar

linguagens
diferentes.

Anatomia
de
um
compilador

Front

End

OMmizador

Back

End

Fortran

COBOL

Lisp

…

ARM

x86

PowerPC

…

Máquinas
Virtuais

•  Uma
máquina
virtual
é
um

hardware
implementado
em

soEware.

•  Porque
isso
é
interessante?

•  Que
linguagens
executam

em
máquinas
virtuais?

•  Ainda
é
necessário
um

tradutor?

Às
vezes,
tudo
é
interpretado

•  Um
interpretador
não
produz
código
de
máquina.

Ao
contrário,
ele
lê
o
código
do
programa
fonte,
e

interpreta
cada
comando
encontrado.

•  Quais
as
vantagens
de
um
interpretador?

•  Quais
linguagens
são

interpretadas?

•  Será
que
há
alguma

linguagem
que

necessariamente
tenha
de

ser
interpretada?

•  Essas
coisas
são
eficiente?

Fazemos
just‐in‐?me

•  Algumas
linguagens
são
compiladas
enquanto

estão
sendo
interpretadas.

–  JavaScript,
por
exemplo.

•  E
de
onde
vem
a
eficiência?

•  Será
que
dá
para
fazer

melhor
que
um
compilador

tradicional?

•  Existe
uma
linguagem
de
programação
“mais

poderosa”
que
todas
as
outras?

•  Se
existe,
que
linguagem
é
essa?

•  Mas
como
medir
esse
“poder”?

Fácil
ou
Di[cil

1.  Encontre
a
rede
de
estradas
mais
curta
que

liga
todas
as
cidades
de
Minas
Gerais.

2.  Encontre
a
menor
rota
passando
por
todas
as

cidades,
sem
repeMr.

3.  Dado
um
programa
P
para
























resolver
(2),
verifique
se
a
























primeira
coisa
que
P


































imprime
é
Nova
Era.

Há
que
sermos
humildes

•  A
máquina
de
Turing
é
um
modelo
téorico
que

define
todos
os
problemas
que
são

computáveis.

– Estado,
fita,
leitor,
símbolos,





















instruções.

•  Se
não
há
solução

















































na
Máquina
de


















































Turing,
então
não














































tem
jeito
mesmo...

Linguagens
Turing‐Completas

•  Se
uma
linguagem
é
equivalente
à
Máquina
de

Turing,
então
ela
é
Turing‐Completa.

•  Quase
toda
LP
é
Turing‐Completa.

•  Mas
existem
linguagens
que
não
o
são.
Algum

exemplo?

Brain‐fuc*

Um
arranjo
muito
grande,
contendo
números.

Oito
comandos:

>
move
uma
posição
para
direita

<
move
uma
posição
para
esquerda

+
soma
um
à
posição
corrente
(PC)

‐
subtrai
um
da
PC

.
imprime
conteúdo
da
PC

,
lê
entrada
e
armazena
na
PC

[
vai
para
comando
após
]
se
PC
é
zero

]
volta
para
comando
após
[
se
PC
não
é
zero.

O
que
estes
programas
fazem?

[-]







ou







[ >+ < - ] 
•  Essas
linguagens
todas
que
a
gente
viu…
Java,

PHP,
C,
Fortran,
COBOL,
Algol,
etc,
etc…
elas

são
muito
parecidas:
variáveis,
loops,

comandos…
Será
que
não
existe
nenhum

outro
paradigma
não?

Linguagens
ImperaMvas
e
DeclaraMvas

•  Linguagens
imperaMvas:

– O
programa
instrui
como
mudar
o
estado
da

máquina.

– Variáveis,
loops,
sequências
de
comandos.

– Efeitos
colaterais.
Existe
função
que
retorna

valores
diferentes
dados
parâmetros
iguais?

•  Linguagens
declaraMvas:

– O
programa
descreve
uma
verdade.

– Ausência
de
efeitos
colaterais.

– Loops
via
chamada
de
funções
recursivas.

SML

•  O
programa
é
um
conjunto
de
funções.

– Programas
são
provas
por
indução.

•  Principais
estruturas
de
dados
são
listas
e

tuplas.

fun sum [] = 0 
 | sum (h::t) = h + sum t 
fun filter [] _ = [] 
 | filter (h::t) f = 
 if (f h) 
 then h :: (filter f t) 
 else (filter f t) 
SorMng

fun leq a b = a <= b 
fun grt a b = a > b 
fun filter _ nil = nil 
 | filter f (h::t) = 
 if f h then h :: filter f t else filter f t 
fun qsort nil = nil 
 | qsort (h::t) = 
 (qsort (filter (grt h) t)) 
 @ [h] @ 
 (qsort (filter (leq h) t)) 
Prolog

•  O
programa
é
um
conjunto
de
restrições:

– Se
A
é
verdade,
e
AB
é
verdade,
então
B
é

verdade.

parent(kim, holly). 
parent(margaret, kim). 
parent(margaret, kent). 
parent(esther, margaret). 
parent(herbert, margaret). 
parent(herbert, jean). 
bisavo(GGP, GGC) :- 
 parent(GGP, GP), parent(GP, P), parent(P, GGC). 
ancestor(X, Y) :- parent(X, Y). 
ancestor(X, Y) :- parent(Z, Y), ancestor(X, Z). 
•  O
que
produzirá

bisavo(X, Y)? 
Um
problema
NP‐completo

sum([],0). 
sum([Head|Tail],X) :- 
 sum(Tail,TailSum), 
 X is Head + TailSum. 
subList([], []). 
subList([H|T], [H|R]) :- subList(T, R). 
subList([_|T], R) :- subList(T, R). 
intSum(L, N, S) :- subList(L, S), sumList(S, N). 
Dada
uma
lista
L
de
números
inteiros,
existe
uma

sublista
S
cuja
soma
seja
N?