Anais do XVII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do II Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
25 e 26 de setembro de 2012
IMPLEMENTAÇÃO E AVALIAÇÃO DE MÉTODOS DE
DESCOBERTA DE SERVIÇOS WEB: AVALIAÇÃO DA
ESTABILIDADE E ROBUSTEZ DE ALGORITMOS DE FILTRAGEM
COLABORATIVA EM FACE DE ATAQUES DE INJEÇÃO DE
PERFIS
Pedro Henrique Grandin
Juan Manuel Adán Coello
Faculdade de Engenharia de Computação
CEATEC
[email protected]
Grupo de Pesquisa em Sistemas Inteligentes
CEATEC
[email protected]
Resumo: Em trabalhos anteriores do Grupo de Pesquisa em Sistemas Inteligentes da PUC-Campinas
foram implementados algoritmos de filtragem colaborativa usando os algoritmos IMEAN, UMEAN, K-nn e
K-means, visando a recomendação de serviços Web
semânticos. Nesses trabalhos, verificou-se que considerar a similaridade semântica entre serviços no
momento de calcular o grau de semelhança entre
usuários e prever avaliações reduz significativamente
o erro médio das previsões feitas em cenários de
dados esparsos. Entretanto, sistemas de recomendação baseados em filtragem colaborativa são abertos por natureza, o que os torna vulneráveis a ataques de injeção de perfis. Neste tipo de ataque, perfis tendenciosos são inseridos na base de dados de
avaliações, o que possibilita que atacantes possam
manipular as recomendações feitas pelo sistema.
Neste plano de trabalho foram avaliadas a estabilidade e a robustez dos algoritmos implementados em
face de ataques de injeção de perfis. O UMEAN
mostrou-se o algoritmo mais tolerante a ataques e o
IMEAN o menos tolerante, sendo que o K-nn e o Kmeans apresentam bom resultados, particularmente
se for considerado que o UMEAN apresenta taxas de
erro elevadas em situações de dados esparsos, como mostram trabalhos anteriores.
Palavras-chave: ataque de injeção de perfil, serviços Web, algoritmos de filtragem colaborativa.
vulneráveis a ataques de injeção de perfis. Neste tipo
de ataque, perfis tendenciosos são inseridos na base
de dados de avaliações, o que permite que atacantes
possam manipular as recomendações feitas pelo
sistema. Seus principais objetivos são elevar o grau
de recomendação (push) ou diminuir o grau de recomendação (nuke) de um item, tendo como alvo um
usuário ou um grupo de usuários [1].
Os tipos de ataques de injeção de perfis mais estudados são o ataque aleatório (random attack), o ataque pela média (average attack), o ataque a segmento (segment attack) e o ataque bandwagon
[1][2][3].
Pretende-se avaliar algoritmos de recomendação
implantados sob a perspectiva da robustez e estabilidade do sistema que os usa. A robustez mede o
desempenho do sistema antes e depois do ataque,
para verificar como o ataque afetou o sistema como
um todo. A estabilidade verifica o desvio nos valores
sugeridos pelo sistema para o item atacado, induzido
pelos perfis de ataque.
As principais métricas de avaliação do sucesso de
um ataque são o desvio de previsão (prediction shift),
a taxa de acerto (hit ratio) [1] e o erro médio absoluto
normalizado (Nomalized Mean Absolute Error –
NMAE) [2] .
Área do Conhecimento: Ciências Exatas e da Terra
– Ciência da Computação.
2.
ALGORITMOS
COLABORATIVA
1. INTRODUÇÃO
Algoritmos de filtragem colaborativa (FC) podem ser
usados para prever o valor que um determinado
usuário (usuário alvo) atribuiria a um item (item alvo)
ainda não avaliado por ele, a partir das avaliações de
outros usuários.
Sistemas de recomendação baseados em filtragem
colaborativa são abertos por natureza, o que os torna
DE
FILTRAGEM
Anais do XVII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do II Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
25 e 26 de setembro de 2012
A previsão pode ser feita por algoritmos simples
como IMEAN (item mean) e o UMEAN (user mean).
O primeiro estima o valor da avaliação de um item
com base na média dos valores das avaliações feitas
por todos os usuários do item alvo. Já o UMEAN
estima o valor da avaliação de um item a partir da
média de todos os itens avaliados pelo usuário alvo.
Entretanto, a literatura mostra que algoritmos mais
elaborados e mais precisos têm sido usados em
sistemas de recomendação baseados em filtragem
colaborativa. Esses algoritmos podem ser de três
tipos: baseado em memória, baseado em modelo e
híbrido [3].
Algoritmos baseados em memória permitem prever
que nota um usuário alvo daria a um item usando
diretamente as avaliações disponíveis. Um exemplo
desse tipo de algoritmo é o K-nn (K-nearest neighbors) que utiliza as avaliações dos K usuários mais
semelhantes ao usuário alvo para prever o valor de
uma avaliação que esse usuário atribuiria a um item
ainda não avaliado por ele.
A figura 1 mostra um exemplo de matriz usuárioitem, que registra os valores das avaliações feitas
por seis usuários para seis itens quaisquer (livros,
filmes, serviços Web etc.). A coluna mais à direita
mostra a similaridade entre Alice e os demais usuários, utilizando a correlação de Pearson, a ser apresentada abaixo. Se for considerado apenas o usuário
mais próximo à Alice (K=1), um algoritmo baseado em
memória preveria que Alice atribuiria ao item 6 um
valor próximo ao atribuído a esse item pelo Usuário 5.
Item Item Item Item Item Item
1
2
3
4
5
6
Alice
5
Usuário 1
2
Usuário 2
3
Usuário 3
2
3
3
Similaridade
com Alice
?
4
4
1
- 1.00
1
3
1
2
0.76
4
2
3
1
1
0.72
Usuário 4
3
3
2
1
3
1
0.21
Usuário 5
4
3
3
3
2
0.94
Figura 1. Exemplo de uma matriz usuário-item
respectivamente; e I o conjunto de todos os item
quem ambos os usuários avaliaram.
Sim(u, v) =
∑iϵI (ru,i – r’u) * (rv,i – r’v)
(∑iϵI (ru,i – r’u)² )
1/2
(1)
1/2
* (∑iϵI (rv,i – r’v)² )
Nos algoritmos baseados em modelo, o valor previsto não é obtido diretamente dos usuários mais próximos, mas sim, através de um modelo formado a
partir dos dados das avaliações disponíveis.
Um exemplo de algoritmo baseado em modelo é o Kmeans, que pode ser utilizado para agrupar perfis de
usuários em K grupos (clusters). Em linhas gerais, o
funcionamento do algoritmo é o seguinte: inicialmente k pontos (vetores de perfis de usuários definidos
pelos valores atribuídos pelos usuários aos itens)
são escolhidos como centróides dos grupos. A seguir
um passo de atribuição e um passo de atualização
são repetidos até a convergência do algoritmo. No
passo de atribuição, cada ponto (perfil) é associado
ao grupo com o centróide mais próximo. No passo de
atualização, os centróides dos grupos são atualizados para a média dos pontos associados ao grupo. O
algoritmo converge quando os centróides tornaremse estáveis, ou seja, não mudarem na fase de atualização. A equação (1) pode ser usada para calcular a
distância entre um usuário e o centróide do grupo.
Algoritmos híbridos buscam combinar as características de algoritmos baseados em memória e em modelo. Este tipo de algoritmo não foi tratado no presente plano de trabalho.
A partir dos k usuários ou grupos mais próximos ao
usuário alvo a equação (2) pode ser usada para prever a nota que o usuário u atribuiria ao item i. Nessa
equação, u representa o usuário alvo e v um usuário
próximo ou um grupo próximo, conforme se esteja
usando o k-nn ou o k-means, respectivamente; rv,i é
o valor da avaliação que v fez do item i; r’v e r’u as
médias das notas atribuídas por v e u,
respectivamente; sim(u,v) a semelhança entre u e v;
e V o conjunto dos vizinhos próximos (usuários ou
grupos) do usuário u.
P(ru,i) = r’u + ( ∑vϵV sim(u,v) (rv,i – r’v)) / ∑vϵV sim(u,v)
A correlação de Pearson, computada pela equação
(1), pode ser usada para determinar o quão semelhantes são dois usuários. Na equação, rv,i e ru,i são
as avaliações dos usuários v e u, respectivamente,
para o item i; r’v e r’u as médias de todas as
avaliações feitas pelos usuários v e u,
(2)
3. TIPOS DE PERFIS DE ATAQUE
Um ataque de injeção de perfis contra um sistema de
recomendação consiste de um conjunto de perfis
adicionados ao sistema pelo atacante. A forma genérica desses perfis é mostrada na figura 2. Cada ele-
Anais do XVII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do II Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
25 e 26 de setembro de 2012
mento i na figura corresponde à avaliação de um
item. Is é um conjunto de itens com valores que caracterizam o tipo de ataque; IF é o conjunto de itens
de preenchimento, usualmente com valores aleatórios, e que irão compor a maior parte das avaliações;
IØ é o conjunto de itens não avaliados, ou de avaliações nulas; e it, representa o item alvo do ataque.
Figura 2. Estrutura de um perfil de ataque; Fonte: [1]
Em [1] apresentam-se quatro tipos de ataques: o
ataque aleatório (random attack), o ataque pela média (average attack), o ataque a segmento (segment
attack) e o ataque bandwagon. Destes, o ataque
aleatório é considerado o mais efetivo e o ataque a
segmento o que oferece o melhor compromisso entre
efetividade e facilidade de ser posto em prática, sendo, por essa razão, esses os ataques que foram
considerados nos experimentos descritos neste artigo.
No ataque aleatório (random attack), os itens em Is
não são preenchidos e os de IF são preenchidos
aleatoriamente, de acordo com a distribuição de
Poisson, obtida a partir das avaliações existentes
para esses itens; e it é preenchido com o valor máximo que uma avaliação pode ter.
No ataque a segmento (segment attack), os itens em
Is permitem definir uma categoria, ou segmento. Esses itens recebem avaliações máximas, quando se
deseja promover um item (push), ou mínimas, quando se deseja rebaixá-lo (nuke). Se esses itens forem,
por exemplo, filmes de terror famosos, o ataque a
segmento estaria voltado a essa categoria. Esse
ataque é notavelmente mais efetivo se seus alvos
também pertencem à mesma categoria [1]. Os valores em IF são preenchidos com a avaliação mínima e
it com a avaliação máxima.
4. MÉTRICAS DE AVALIAÇÃO
Para que se possa medir a efetividade de ataques
em uma determinada situação e ambiente é preciso
definir que métricas serão utilizadas.
Uma das métricas mais utilizadas para isso é o desvio de previsão (prediction shift), calculado pela equação (3), onde P’(ru,i) é o valor previsto para a avaliação que o usuário u faria do item i depois do ata-
que e P(ru,i) representa o valor previsto antes do ataque.
∆ u, i = P’ (ru,i) - P(ru,i)
(3)
Um desvio de previsão positivo indica que o ataque
teve sucesso em fazer o item mais positivamente
avaliado. Todavia, um aumento elevado do desvio de
previsão não garante que um item será recomendado. É possível que outros itens também sejam afetados pelo ataque ou que o item fosse inicialmente
avaliado com um valor muito baixo de modo que
mesmo um desvio elevado não o coloque na categoria de recomendável.
Sendo assim, foi utilizada também a métrica taxa de
acerto (hit ratio), que mede a eficácia do ataque sobre um item comparado com outros itens. A taxa de
acerto é calculada pela equação (4), onde Hui será
igual a 1 se o item i aparecer na lista dos N itens
recomendados ao usuário u (top-N recommendations), em caso contrário seu valor será 0; UT é o
conjunto de usuários alvo.
Hit Ratio i = ∑ H u,i / |UT|
(4)
uϵUT
Foi utilizada também a métrica erro médio absoluto
(Mean Absolute Error – MAE), obtida a partir da diferença entre os valores previstos para as avaliações
do usuário e os valores reais dessas avaliações,
calculados pela equação (5), onde ru,i é a nota real
atribuída pelo usuário u ao item i, r’u,i a nota prevista
pelo algoritmo para esse item e N o número de notas
previstas pelo algoritmo.
MAE = ∑ u,i | r u,i – r’ u,i | / N
(5)
Para calcular o MAE, foram feitos vários experimentos para que fosse possível calcular a variação dos
resultados e obter um resultado com a média desses
erros. O MAE foi normalizado de modo a torná-lo
independente da escala de avaliações usada, dando
origem ao erro médio absoluto normalizado, ou
NMAE (Normalized Mean Absolute Error), calculado
pela equação (6).
NMAE = MAE / (∑ u,i r u,i / N)
(6)
Anais do XVII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do II Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
25 e 26 de setembro de 2012
5. AVALIAÇÃO EXPERIMENTAL
Os experimentos realizados tiveram por objetivo
avaliar o impacto dos ataques de injeção de perfis
dos tipos aleatório e segmento sobre os algoritmos
de filtragem colaborativa IMEAN, UMEAN, K-nn e Kmeans implementados por Ming [5] no sistema
OWLS-MX versão 2.2, [4]. Nos experimentos, os
itens da matriz usuário-item consistem de serviços
Web semânticos do repositório que acompanha esse
sistema.
A matriz usuário-item e os ataques foram elaborados
seguindo a abordagem utilizada em [1]. Foram criados 50 usuários, sendo 20 classificados como “turistas” e 30 como “estudantes”. Os itens a serem avaliados totalizam 108 serviços, incluindo serviços relacionados aos assuntos “carros”, “comida”, “livros”,
“hotéis”, “câmeras”, “publicações”, “surf” e “filmes”.
Cada usuário avaliou 18 serviços de modo a caracterizar seu grupo. Um turista, por exemplo, se interessaria mais em hotéis que estudantes, e, portanto, há
a possibilidade de encontrar mais avaliações positivas de hotéis no grupo dos turistas que no grupo dos
estudantes.
Os perfis de ataque continham 6% do total de serviços avaliados como filler size (IF na figura 2). A quantidade de perfis de ataque foi de 15% do total de
usuários, resultado na injeção de oito usuários atacantes, todos com objetivo de promover um item
(push), o objetivo mais comum de ataques [1]. Para
alvos, foram escolhidos aleatoriamente 5 usuários e
4 serviços, que correspondem a aproximadamente
5% do total de usuários e 3% do total de itens, respectivamente, seguindo a proporção dos experimentos descritos em [1].
A escolha dos itens para o preenchimento do ataque
aleatório é feita automaticamente após especificar a
quantidade de perfis a serem criados. No ataque a
segmento, foi escolhido manualmente um segmento
caracterizado por três itens (IS). O segmento escolhido para os ataques foi o de “comida”, pois se presume que tanto os estudantes quanto os turistas se
interessariam por comida, de modo que essa escolha
deve afetar ambos os grupos de usuários.
6. RESULTADOS E DISCUSSÕES
Após realizar os testes com base no algoritmo
UMEAN, foi possível perceber que se tratava de um
algoritmo imune aos ataques, o que faz sentido, já
que a adição de perfis não interfere na previsão de
uma avaliação, pois a nota prevista para um item é a
média das avaliações feitas pelo usuário alvo. O
NMAE para o algoritmo foi de 0,33111, com e sem
ataque, conforme mostrado na tabela 1.
Tabela 1. NMAE dos algoritmos avaliados
Sem ataque
Ataque
aleatório
Ataque a
segmento
UMEAN
0,33111
0,33111
0,33111
IMEAN
0,33064
0,48232
0,47835
K-nn
0,27781
0,28239
0,28415
K-means
0,29305
0,30015
0,30193
Para o algoritmo IMEAN esperava-se que os ataques
tivessem grande impacto no NMAE e na taxa de
acerto, já que suas previsões são baseadas inteiramente nos demais usuários, o que é confirmado pela
tabela 1 e pela figura 3. Nessa figura, o eixo das
abscissas representa a quantidade de itens (serviços) com as melhores avaliações que serão recomendadas ao usuário, os tops-N itens. O eixo das
ordenadas representa o taxa de acerto em valores
absolutos, lembrando que quanto mais próximo ao
valor 1, mais itens alvo serão recomendados aos
usuários.
Figura 3. Taxa de acerto do algoritmo IMEAN
Observa-se que tanto o ataque aleatório quanto o
ataque a segmento apresentaram resultados semelhantes. Isso acontece, pois para que seja feito o
cálculo do IMEAN, são usadas as avaliações dos
itens alvo de todos os usuários, o que leva os dois
tipos de ataques a efeitos semelhantes nesse con-
Anais do XVII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do II Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
25 e 26 de setembro de 2012
texto. De toda forma, ambos os ataques foram efetivos, resultando e um desvio de previsão igual a
2,70966 e a um NMAE de 0,48232, para o ataque aleatório e de 0,47835 para o ataque a segmento, versus
0,33064 sem ataque, conforme mostrado na tabela 1.
figura 5, e uma semelhança mínima de 50% para o
algoritmo K-means, resultando a figura 6.
Para a avaliação da taxa de acerto dos algoritmos Knn e K-means, variou-se o valor de semelhança mínima entre os usuários (K-nn) e entre um usuário e o
centróide de um grupo (K-means) usada no momento de escolher os K vizinhos mais próximos e, assim,
aplicar a equação 2. Além disso, deixou-se fixo o
número de usuários semelhantes (cinquenta) e o
número de clusters (dois) a utilizar durante a realização dos testes. A figura 4 apresenta os resultados
para o algoritmo K-nn e para o algoritmo K-means.
Figura 5. Taxa de acerto do algoritmo K-nn
Figura 4. Desvio de previsão dos algoritmos K-nn e Kmeans em função da similaridade mínima entre usuários
Observe-se que a partir de uma semelhança entre
usuários de 20% para o algoritmo K-nn e de 70% para
o K-means, o desvio de previsão permanece com valor
zero, o que significa que, a partir desses valores a semelhança exigida foi suficiente para que não fossem
incluídos os perfis de ataque no cálculo de previsão das
notas, levando assim a uma constante 0 de desvio de
previsão.
Para analisar a taxa de acerto foram escolhidos valores
de similaridade que resultaram em um desvio de previsão alto e que estivessem próximos ao valor em que o
desvio cai a zero. Os valores adotados foram de 5%
para o algoritmo K-nn, obtendo como resultado a
Figura 6. Taxa de acerto do algoritmo K-means
Nota-se na figura 5 que os ataques tiveram efeito sobre
a taxa de acerto a partir do top 20, destacando-se que
o ataque a segmento tem maior eficácia para o top 20,
40 e 50. O efeito dos de ambos os ataques sobre o
NMAE é pequeno, conforme mostrado na tabela 1.
A figura 6 mostra que para o K-means só se observa
uma variação nas curvas para o top 50 e 60. O efeito
sobre o NMAE também foi pequeno, conforme mostra a tabela 1.
Anais do XVII Encontro de Iniciação Científica – ISSN 1982-0178
Anais do II Encontro de Iniciação em Desenvolvimento Tecnológico e Inovação – ISSN 2237-0420
25 e 26 de setembro de 2012
7. CONCLUSÃO
Os experimentos realizados para avaliar a estabilidade e robustez dos algoritmos IMEAN, UMEAN, Knn e K-means, implementados em [5] para a recomendação de serviços Web semânticos, em face de
ataques de injeção de perfis, mostraram que o algoritmo UMEAN não é afetado pelos ataques e que o
IMEAN é o mais sensível a esses ataques. Entretanto esses dois algoritmos são usados apenas como
um referencial para a análise dos demais algoritmos,
já que ambos apresentam baixa precisão em suas
previsões, particularmente quando a matriz usuárioitem é esparsa, como mostrado em [5], não sendo
utilizados por sistemas de recomendação atuais.
Nos experimentos apresentados, verificou-se que o
K-nn permite atingir um desvio de previsão próximo a
zero para taxas de semelhança entre usuários consideravelmente reduzida (20%), enquanto que no kmeans isso só é possível para valores mais elevados
(70%). Por outro lado, nos experimentos apresentados para analisar a taxa de acerto, o K-means apresenta melhores resultados. No entanto, é importante
notar que nesses experimentos foi utilizado para o Knn um valor de semelhança entre usuários muito
inferior ao utilizado em K-means. Com valores elevados de semelhança entre usuários, o K-nn apresenta
melhores resultados também neste quesito. Em contraposição, a literatura mostra que o K-means é mais
escalável que o K-nn.
Os algoritmos foram também avaliados considerando
a utilização do valor da similaridade semântica entre
serviços Web quando do cálculo da semelhança
entre usuários utilizando a correlação de Pearson e
no momento de prever o valor de uma avaliação,
conforme discutido em [5]. Constatou-se que essa
abordagem não influenciou de forma significativa os
resultados, o que confirma os resultados de [5], onde
se verificou que a semelhança entre serviços afeta
de forma relevante a precisão dos algoritmos apenas
quando a matriz usuário-item é esparsa. Recomenda-se que em trabalhos futuros sejam feitos experimentos para avaliar o comportamento dos algoritmos
em face de ataques também em situações de dados
esparsos.
8. AGRADECIMENTOS
Agradeço ao CNPq pela bolsa de iniciação científica
que possibilitou a execução desse projeto, à Pontifícia Universidade Católica de Campinas-SP pela oportunidade de realizar este trabalho e à atenção e
motivação do orientador Prof. Dr. Juan Manuel Adán
Coello.
9. REFERÊNCIAS
[1] B. Mobasher, R. Burke, R. Bhaumik, and C. Williams, “Toward trustworthy recommender systems: An analysis of attack models and algorithm
robustness,” ACM Transactions on Internet Technology (TOIT), vol. 7, no. 4, p. 23–es, 2007.
[2] J. J. Sandvig, B. Mobasher, and R. Burke, “A survey of collaborative recommendation and the robustness of algorithms,” IEEE Data Engineering
Bulletin, vol. 31, no. 2, pp. 3–13, 2008.
[3] X. Su and T. M. Khoshgoftaar, “A survey of collaborative filtering techniques,” Advances in Artificial Intelligence, vol. 2009, p. 4, 2009.
[4] M. Klusch, B. Fries, and K. Sycara, “OWLS-MX: A
hybrid Semantic Web service matchmaker for
OWL-S services,” Web Semantics: Science, Services and Agents on the World Wide Web, vol. 7,
no. 2, pp. 121–133, 2009.
[5] Y. Yuming, "Algoritmos de previsão de avaliação
de serviços Web semânticos", Trabalho de Conclusão de Curso, Faculdade de Engenharia de
Computação, PUC-Campinas, 2010.
[6] B. Mobasher, R. Burke, J.J. Sandvig, "ModelBased Collaborative Filtering as a Defense
Against Profile Injection Attacks", Center for Web
Intelligence - Information Systems Journal, 2006 AAAI Press.