Detecção Distribuída de Violação de Integridade em Sistemas com Conteúdo Replicado
Abstract
This work presents a new comparison-based diagnosis model and a new algorithm, called Hi-Dif, based on this model. The algorithm is used for checking the integrity of systems with replicated data, for instance, unauthorized Web page modifications. Fault-free nodes running Hi-Dif send a test to two other nodes and the test results are compared. Based on task results, tested nodes are classified in sets. 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 task results. One of the sets always contains all fault-free nodes. One fundamental difference of the proposed model to previously published models is that the new 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; that the maximun number of tests required is O(N2) in the worst case; and, that the algorithm is (N–1)-diagnosable. Experimental results obtained by simulation and by the implementation of the algorithm applied to the Web are presented.
References
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.
