Detecção Distribuída de Alterações em Sistemas Com Conteúdo Replicado Utilizando Diagnóstico Baseado em Comparações

Roverli P. Ziwich
Dissertação de Mestrado,
Universidade Federal do Paraná, Dept. Informática. Curitiba, PR, Brazil.


Membros da Banca:
Prof. Djamel Fawzi Hadj Sadok (CIN, UFPE),
Prof. André Luiz Pires Guedes (PPGInf/UFPR),
Prof. Luiz Carlos Pessoa Albini (Unicenp),
Prof. Elias P. Duarte Jr. (Orientador - PPGInf/UFPR).
Data da Defesa: 17/08/2004.  [pdf]  dspace.c3sl.ufpr.br



Resumo

Este trabalho apresenta um novo modelo genérico de diagnóstico hierárquico adaptativo distribuído e baseado em comparações e um novo algoritmo, chamado Hi-Dif, que se baseia neste modelo. O algoritmo permite a detecção de alterações em sistemas com conteúdo replicado distribuído em uma rede como, por exemplo, a Internet. 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 do sistema. 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 log2N rodadas de testes; o número máximo de testes requeridos pelo algoritmo é de O(N2) 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.


Abstract

This work presents a new comparison-based distributed system-level diagnosis generic model and a new algorithm, called Hi-Dif, based on this model. The algorithm allows the detection of modifications in systems with replicated data distributed on networks like the Internet. Fault-free nodes running Hi-Dif, execute tests on other nodes. Based on test results tested nodes are classified in sets. A test consists of a task that is sent to two system nodes. After the tasks are executed, the task outputs is sent back to the tester. The outputs are then compared; if the comparison produces a match, the two nodes are classified in the same set. On the other hand, if the comparison results in a mismatch, the two nodes are classified in different sets, according to their tasks results. One of the sets always contain all fault-free nodes. One fundamental difference of the proposed model to previously published models is that this model allows the task outputs of two faulty nodes to be equal to each other. Considering a system of N nodes, it is proved that the algorithm has latency equal to log2N testing rounds; the maximun number of tests required for the algorithm is O(N2) in the worst case; and, the algorithm is (N–1)-diagnosable. Experimental results obtained by simulation and by the implementation of the algorithm applied to the Web are presented.


Referências Bibliográficas

[1]   NUA.COM. How Many Online, http://www.nua.ie/surveys/how_many_online /world.html, Acessado em 02/10/2003.

[2]   CERT Coordination Center, http://www.cert.org, Acessado em 03/10/2003.

[3]   E. P. Duarte Jr., G. Mansfield, S. Noguchi, M. Miyazaki, “Fault-Tolerant Network Management,” Proc. ISACC’94, Monterrey, Mexico, 1994.

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

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

[6]   IDG Now! - Hackers brasileiros lideram ranking de invasões em 2001, http://idgnow.terra.com.br/idgnow/internet/2002/01/0009, Acessado em 27/09/2003.

[7]   IDG Now! - Cresce o número de invasões a sites Linux, http://idgnow.terra.com.br/idgnow/internet/2002/07/0046, Acessado em 05/10/2003.

[8]   D. Russel, G. T. Gangemi, Computer Security Basics. O’Reilly, 1992.

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

[10] 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.

[11] L. Liu, C. Pu, W. Tang, “WebCQ – Detecting and Delivering Information Changes on the Web,” Proceedings of International Conference on Information and Knowledge Managemente (CIKM), pp. 512-519, Nov. 2000.

[12] F. Douglis, T. Ball, “Tracking and Viewing Changes on the Web,” 1996 USENIX Techinical Conference, pp. 165-176, 1996.

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

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

[15] D. Faensen, L. Faulstich, H. Schweppe, A. Hinze, A. Steidinger, “Hermes – A Notification Service for Digital Libraries,” ACM/IEEE JCDL’01, pp. 373-380, Jun. 2001.

[16] T. Catarci, “Web-based Information Access,” IEEE Proceedings of the 4th IECIS International Conference on Cooperative Information Systems (CoopIS), Edinburgo, Escócia, pp. 10-19, 1999.

[17] 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.

[18] N. Glance, J.-L. Meunier, P. Bernard, D. Arregui, “Colaborative Document Monitoring,” Proceedings of the 2001 International ACM SIGGROUP Conference on Supporting Group Work, Boulder, CO, 2001.

[19] 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.

[20] S. Flesca, F. Furfaro, E. Masciari, “Monitoring Web Information Changes,” International Conference on Information Technology: Coding and Computing (ITCC’01), Abr. 2001.

[21] G. Masson, D. Blough, G. Sullivan, “System Diagnosis,” in Fault-Tolerant Computer System Design, D.K. Pradhan, Prentice-Hall, 1996.

[22] F. Preparata, G. Metze, R. T. Chien, “On The Connection Assignment Problem of Diagnosable Systems,” IEEE Transactions on Computers, Vol. 16, pp. 848-854, 1968.

[23] S. L. Hakimi, K. Nakajima, “On Adaptive System Diagnosis,” IEEE Transactions on Computers, Vol. 33, pp. 234-240, 1984.

[24] R. P. Bianchini, R. Buskens, “An Adaptive Distributed System-Level Diagnosis Algorithm and Its Implementation,” Proc. FTCS-21, 1991.

[25] P. Jalote, Fault Tolerance in Distributed Systems. Prentice Hall, 1994.

[26] E. P. Duarte Jr., T. Nanya, “A Hierarquical Adaptive Distributed System-Level Diagnosis Algotithm,” IEEE Transactions on Computers, Vol. 47, No.1, pp. 34-45, Jan 1998.

[27] R. P. Bianchini, R. Buskens, “Implementation of On-Line Distributed System-Level Diagnosis Theory,” IEEE Transactions on Computers, Vol. 41, pp. 616-626, 1992.

[28] A. Brawerman, E. P. Duarte Jr., “A Synchronous Testing Strategy for Hierarchical Adaptive Distributed System-Level Diagnosis,” Proc. IEEE LATW'00, pp. 154-161, 2000.

[29] 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.

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

[31] 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.

[32] 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.

[33] A. Sengupta, A. T. Dahbura, “On Self-Diagnosable Multiprocessor Systems: Diagnosis by Comparison Approach,” IEEE Transactions on Computers, Vol. 41, No. 11, pp. 1386-1396, 1992.

[34] 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.

[35] 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.

[36] G. S. Almasi, A. Gottlieb, Highly Parallel Computing, The Benjamim/Commings Publishing Company Inc., 1994.

[37] C. Xavier, S. S. Iyengar, Introduction to Parallel Algorithms, Wiley-Intersciense Publication, 1998.

[38] N. F. Tzeng, S. Wei, “Enhanced Hypercubes,” IEEE Transactions on Computers, Vol. 40, No. 3, pp. 284-294, Mar. 1991.

[39] T. Araki, Y. Shibata, “Diagnosability of Butterfly Networks under the Comparison Approach,” IEICE Trans. Fundamentals, Vol E85-A, No. 5, Maio 2002.

[40] F. T. Leighton, Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes, Morgan Kaufmann, San Mateo, CA, 1992.

[41] J. Fan, “Diagnosability of Crossed Cubes,” IEEE Transactions on Computers, Vol. 13, No. 10, pp. 1099-1104, Out. 2002.

[42] E. P. Duarte Jr., L. C. P. Albini, A. Brawerman, A. L. P. Guedes, “A Hierarchical Distributed Diagnosis Algorithm with Detours,” Technical Report 002/2003, Universidade Federal do Paraná, Dept. Informática http://www.inf.ufpr.br/info/techrep, 2003.

[43] L. C. P. Albini, E. P. Duarte Jr., “Generalized Distributed Comparison-Based System-Level Diagnosis,” 2nd IEEE Latin American Test Workshop, pp. 285-290, Set. 2001.

[44] S. L. Hakimi, A. T. Amin, “Characterization of Connection Assignment of Diagnosable Systems,” IEEE Transactions on Computers, Vol. 23, pp. 86-88, 1974.

[45] S. Rangarajan, A. T. Dahbura, E. A. Ziegler, “A Distributed System-Level Diagnosis for Arbitrary Network Topologies,” IEEE Transactions on Computers, Vol. 44, pp. 312-333, 1995.

[46] V. Hadzilacos, S. Toueg, Fault-Tolerant Broadcasts and Related Problems, “Distributed Systems,” S. Mullender, ACM Press, Cap. 5, 1993.

[47] T. Araki, Y. Shibata, “Efficient Diagnosis on Butterfly Networks under the Comparison Approach,” IEICE Trans. Fundamentals, Vol E85-A, No. 4, Abr. 2002.

[48] K. Efe, “A Variation on de Hypercube with Lower Diameter,” IEEE Transactions on Computers, Vol. 40, No. 11, pp. 1312-1316, Nov. 1991.

[49] K. Efe, “The Crossed Cube Architecture for Parallel Computing,” IEEE Transactions on Parallel and Distributed Systems, Vol. 3, No. 5, pp. 513-524, Set. 1992.

[50] K. Efe, P. K. Blackwell, W. Slough, T. Shiau, “Topological Properties of the Crossed Cubes Architecture,” IEEE Transactions on Computers, Vol. 44, No. 7, pp. 923-929, Jul. 1995.

[51] F. Harary, Graph Theory, Addison-Wesley Publishing Company, 1971.

[52] R. Gould, Graph Theory, The Benjamim/Cummings Publishing Company Inc., 1988.

[53] E. P. Duarte Jr., L. C. E. Bona, “A Dependable SNMP-based Tool for Distributed Network Management,” Proc. IEEE/IFIP International Conference on Dependable Systems and Networks (DSN'2002), Dependable Computing and Communications (DCC) Symposium, Washington D. C., USA, 2002.

[54] M. H. MacDougall, Simulating Computer Systems: Techniques and Tools, The MIT Press, Cambridge, MA, 1987.

[55] B. W. Kernighan, D. M. Ritchie, The C Programming Language, Prentice Hall, 2a ed., 1988.

[56] The Linux Home Page at Linux Online, http://www.linux.org, Acessado em 23/07/2004.

[57] D. E. Comer, Internetworking with TCP/IP – Principles, Protocolos, and Architectures, Prentice Hall, 4a ed., Vol. 1, 1995.

[58] Intel Corporation, http://www.intel.com, Acessado em 23/07/2004.

[59] Guia do Hardware.Net – htto://www.kurumin.com.br, Acessado em 23/07/2004.

[60] Rivest R, “The MD5 Message-Diggest Algorithm,” RFC 1321, IETF, Abr. 1992