Linguagens de Programação

Prévia do material em texto

Fernando	Magno	Quintão	Pereira	
Linguagens	de	Programação	
L A B O R A T O R I O D E C O M P I L A D O R E S
Department of Computer Science − Universidade Federal de Minas Gerais − Brazil
•  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	é	Zero	
Se	Zero,	então	vá	para	.L4	
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	
•  Deste	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	
cienyficos.	
•  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	esta	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 thepolicy 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 with
an “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 line 14 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	este	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	esta	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	
soDware.	
•  Porque	isto	é	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	é	esta?	
•  Mas	como	medir	este	“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	daPC	
.	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	são	instruções.	
– Atribuições,	loops,	sequências.	
– Efeitos	colaterais	e	estado.	
•  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?	
Por	que	saber	mais	sobre	LPs?	
•  Porque	elas	estão	aí!	
•  Algumas	disputas	são	
fascinantes.	
•  A	história	delas	é	
incrível.	
•  Diferentes	problemas	
pedem	diferentes	
soluções.