Detecção Distribuída de Violação de Integridade em Sistemas com Conteúdo Replicado

Roverli Pereira Ziwich; Elias Procópio Duarte Jr.; Luiz Carlos Pessoa Albini

doi:10.5753/sbseg.2005.21528

Roverli Pereira Ziwich UFPR
Elias Procópio Duarte Jr. UFPR
Luiz Carlos Pessoa Albini UNICEMP

DOI: https://doi.org/10.5753/sbseg.2005.21528

Resumo

Este trabalho apresenta um novo modelo de diagnóstico baseado em comparações e um novo algoritmo, chamado Hi-Dif para a detecção de alterações em sistemas com conteúdo replicado. Um nodo sem-falha executando o algoritmo Hi-Dif, testa outro nodo do sistema para classificar seu estado. O modelo classifica os nodos do sistema em conjuntos de acordo com o resultado dos testes. Um teste é realizado através do envio de uma tarefa para um par de nodos. Após o recebimento das duas saídas da execução destas tarefas, o testador compara estas saídas e, se a comparação indicar igualdade, os nodos são classificados no mesmo conjunto. Por outro lado, se a comparação das saídas indicar diferença, os nodos são classificados em conjuntos distintos, de acordo com o resultado da tarefa. Um dos conjuntos contém os nodos sem-falha do sistema. Uma diferença fundamental do modelo proposto para outros modelos publicados anteriormente é que a comparação por um nodo sem-falha, sobre as saídas produzidas por dois nodos falhos, pode resultar em igualdade. Considerando um sistema com N nodos, prova-se que o algoritmo Hi-Dif possui latência igual a log₂N rodadas de testes; que o número máximo de testes requeridos pelo algoritmo é de O(N²) no pior caso; e, que o algoritmo é (N–1)-diagnosticável. Resultados experimentais obtidos através de simulações e através de implementação do algoritmo aplicado à Web são apresentados.

Referências

CERT Coordination Center, http://www.cert.org, Acessado em 05/09/2004.

ALDAS, Analytisches Labor Dr. Axel Schumann, http://www.aldas.de, Acessado em 05/10/2003.

S. Garfinkel, G. Spafford, e A. Schwartz, Practical Unix & Internet Security, O'Reilly, 3a. ed., Fev. 2003.

A. Subbiah, D. M. Blough, "Distributed Diagnosis in Dynamic Fault Environments," IEEE Transaction on Parallel and Distributed Systems, Vol 15, No. 5, pp. 453-467, Mai. 2004.

L. C. P. Albini, E. P. Duarte Jr., "Generalized Distributed Comparison-Based SystemLevel Diagnosis," 2nd IEEE Latin American Test Workshop, pp. 285-290, Set. 2001.

D. Ingham, S. K. Shrivastava, F. Panzieri, "Constructing Dependable Web Services," IEEE Internet Computing, Vol 4, No. 1, pp 25-33, Jan/Fev 2000.

B. Tan, S. Foo, S. C. Hui, "Monitoring Web Information Using PBD Technique," Proc. 2nd International Conference on Internet Computing (IC'2001), Las Vegas, USA, pp. 666-672, Jun. 2001.

Url Minder, http://www.netmind.com/URL-minder/URL-minder.html. Acessado em 22/09/2003.

B. Lu, S. C. Hui, Y. Zhang, "Personalized Information Monitoring Over the Web," 1st International Conference on Information Technology & Applications (ICITA 2002), Nov. 2002.

V. Boyapati, K. Chevrier, A. Finkel, N. Glance, T. Pierce, R. Stockton, C. Whitmer, "ChangeDetectorTM: A Site-Level Monitoring Tool for the WWW," International World Wide Web Conference, Hawaii, USA, pp. 570-579, Mai. 2002.

S.-J. Lim, Y.-K. Ng, "An Automated Change-detection Algorithm for HTML documents Based on Semantic Hierachies," Proceedings of the 17th International Conference on Data Engineering (ICDE'01), Heidelberg, Alemanha, pp. 303-312, Abr. 2001.

M. Malek, "A Comparison Connection Assignment for Diagnosis of Multiprocessor Systems," Proc. 7th International Symp. Computer Architecture, pp. 31-36, 1980.

K. Y. Chwa, S. L. Hakimi, "Schemes for Fault-Tolerant Computing: A Comparison of Modularly Redundant and t-Diagnosable Systems," Information and Control, Vol. 49, pp. 212-238, 1981.

J. Maeng, M. Malek, "A Comparison Connection Assignment for Self-Diagnosis of Multiprocessor Systems," Digest 11th Internationall Symp. Fault Tolerant Computing, pp. 173-175, 1981.

A. Sengupta, A. T. Dahbura, "On Self-Diagnosable Multiprocessor Systems: Diagnosis by Comparison Approach," IEEE Transactions on Computers, Vol. 41, No. 11, pp. 13861396, 1992.

D. M. Blough, H. W. Brown, "The Broadcast Comparison Model for On-Line Fault Diagnosis in Multicomputer Systems: Theory and Implementation," IEEE Transactions on Computers, Vol. 48, pp. 470-493, 1999.

D. Wang, "Diagnosability of Hipercubes and Enhanced Hypercubes under the Comparison Diagnosis Model," IEEE Transactions on Computers, Vol. 48, No. 12, pp. 1369-1374, 1999.

T. Araki, Y. Shibata, "Diagnosability of Butterfly Networks under the Comparison Approach," IEICE Trans. Fundamentals, Vol E85-A, No. 5, Mai. 2002.

J. Fan, "Diagnosability of Crossed Cubes," IEEE Transactions on Computers, Vol. 13, No. 10, pp. 1099-1104, Out. 2002.

E. P. Duarte Jr., A. Brawerman, L. C. P. Albini, "An Algorithm for Distributed Hierarquical Diagnosis of Dynamic Fault and Repair Events," Proc. IEEE International Conference on Parallel and Distributed Systems 2000, pp. 299-306, 2000.