Upload
trandat
View
226
Download
0
Embed Size (px)
Citation preview
Técnicas para Análise de Similaridade
de Código de Software em
Litígios de Propriedade Intelectual
PSI5007 - prof. Volnys Bernal
Ana Maria Mota ([email protected])
Denise Hideko Goya ([email protected])
Questão Legal
z No Brasil:
y Autoria de programas: Direito Autoral
y Registro opcional junto ao INPIx Documentos do Programa
z Nos EUA:
y Critérios de aceitação de prova:x Look and Feel
x Abstraction, Filtration, Comparison
y Software é patenteável
Similaridade de Código
z O que é similaridade de código?
z Definir similaridade para que propósito?
y Comparação de programasx detectar roubo de propriedade intelectual
x refatoração / manutenção / reengenharia
x compactação de arquivos
y Comparação de outros tipos de documentos
z O propósito influencia a definição e a técnica
Exemplo: Sintaxe Semelhante
int sum = 0 ;
void foo (Iterator iter){
for ( item = first(iter); has more(iter); item = next(iter) ) { sum = sum + value ( item ) ;
}
}
int bar (Iterator iter){
int sum = 0 ;
for ( item = first(iter); has more(iter); item = next(iter) ) { sum = sum + value ( item ) ;
}
}
Exemplo: Sintaxe Diferente
while ( (x = pi[t-1]) != '(' && x != '+' && x != '-') { posf[j++] = x;
--t;
}
while (1) {
x = pi[t-1];
if (x == '(' || x == '+' || x == '-')
break;
--t;
posf[j++] = x;
}
Tipos de Similaridade e Técnicas
Similaridade Textual
Similaridade por Métricas
Similaridade Baseada em Características
Informação Compartilhada
Similaridade na Curva de Execução
Similaridade na Relação entre Entradas e Saídas
Distância Semântica
Distância na Equivalência da Abstração
Grafo de Dependências do Programa
Similaridade
Representacional
(Sintática)
Similaridade
Comportamental
(Semântica)
Classificação de Similaridade para Código de Software
Sintática - Textual
z Algoritmos clássicos para comparação destrings
z Subseqüência Comum mais Longa (LCS)
y diff (do Unix)
z Diferença de Levenshtein
Diferença de Levenshtein entre "caro" e "clara" é 2:
caro � cara (substituição)
cara � clara (inserção)
Sintática - Textual por Token
z Transformação inicial de strings para tokens
z Comparam-se seqüências de tokens
z Hash para otimização
z Estrutura de dados: árvore de sufixos
a seguinte instrução no código-fonte:
a = b==c : v[i] ? v[0]; // comentário
é transformada e parametrizada para:
v1=v2==v3:v4[v5]?v5[0];
Sintática - por Métricas
z Contagem de atributos do programay número de chamadas de funções
y número de variáveis locais usadas ou definidas
y número de variáveis não-locais usadas ou definidas
y número de parâmetros
y número de sentenças
y número de desvios
y número de loops
z Fórmula sobre os valores acima: score
Sintática - Baseada em Características
z k-gramas: strings de comprimento k
y Algoritmo de Karp-Rabin
y Divide-se o texto em vários k-gramas
y Calcula-se hash de cada k-grama
y Seleciona-se, por exemplo, os hashesmúltiplos de um número dado: fingerprint
z janela de tamanho w: são w hashesconsecutivos de k-gramas
Sintática - Informação Compartilhada
z Medida de similaridade a partir da
y Teoria da Informação de Shannonx entropia (baixa entropia → alta redundância)
y Complexidade de Kolmogorov
y Quantidade de informação compartilhada
Ferramentas
Ferramentas
Textual
diff, Duploc, dup, siff, Plague, Yap,
Jplag, CodeMatch, CCFInder,
CloneDr
por Métricas Clan, Accuse, Yap3, Faidhi-Robson
Baseada em Características Karp-Rabin, Moss
Informação Compartilhada Sid
Curva de Execução
Relação entre Entradas e
Saídas
Distância Semântica
Distância na Equivalência da
Abstração
Grafo de Dependências do
ProgramaDuplix
Similaridade
Representacional
(Sintática)
Similaridade
Comportamental
(Semântica)
Classificação de Similaridade
Conclusões
z Perito deve determinar o que comparar
y abstrair, filtrar, análise manual
z Ferramentas de análise sintática:
y Versões comerciais: CodeSuite e MossPlus
y Versões on-line: Jplag, Moss e SID
z Comparativos entre ferramentasexistentes: analisar com critério