Information Flow in Datalog using Very Naive and Semi Naive Bottom-Up Evaluation Techiques

Antoun Jacques Yaacoub, Ali Awada


Information flow in logic programming is well defined using the usual top-down evaluation approach. In this paper, we tackle the same question using a buttom up evaluation approach using two algorithms, Very Naive and Semi Naive algorithms. We will show that, using these techniques, the existence of the information flow is decidable, so that the flow of information can be detected in all cases. Finally, we will study the computational complexities of each decision problem and prove that it's EXPTIME-complete.

Full Text:



BELL,D. AND LAPADULA,L. Secure Computer Systems: Mathematical Foundations and Model. The MITRE Corporation Bedford MA Technical Report M74244, 1973, vol. 1.

FOLEY, S. A model for secure information flow. Security and Privacy, 1989. Proceedings., 1989 IEEE Symposium on, 1989, p. 248-258.

DENNING, D. A lattice model of secure information flow. Commun. ACM 19, 5 (May 1976), 1976, p. 236-243.

GOGUEN, J. AND MESEGUER, J. Security policies and security models. IEEE Symposium on Security and Privacy, 1982, p. 11-20.

DENNING, D. AND DENNING, P. Certification of programs for secure information flow. Commun. ACM 20, 7 (July 1977), 1977, p. 504-513.

FENTON, J. Memoryless subsystems The Computer Journal, 17, 1974, p. 143-147.

DENNING, D. Cryptography and Data Security, Addison-Wesley, 1982.

DETREVILLE, J.. Binder, a Logic-Based Security Language. Proceedings of the 2002 IEEE Symposium on Security and Privacy (SP ’02). IEEE Computer Society, Washington, DC, USA, 2002.

BERTINO, L. CATANIA, B. FERRARI, E. AND PERLASCA, P. A logical framework for reasoning about access control models. Proceedings of the sixth ACM symposium on Access control models and technologies (SACMAT ’01), 2001, p. 41-52.

WANG, L. WIJESEKERA, D. AND JAJODIA, S. A logic based framework for attribute based access control. Proceedings of the 2004 ACM workshop on Formal methods in security engineering (FMSE ’04), 2004, p. 45-55.

BAI, Y. AND KHAN, K. A modal logic for information system security. Proceedings of the Ninth Australasian Information Security Conference - Volume 116 (AISC ’11), 2011, p. 51-56.

COETZEE, M. AND ELOFF, J.H.P. A logic-based access control approach for Web Services ISSA 2004 (Information Security for South Africa), 2004.

BALBIANI, P., AND YAACOUB, A. Deciding the bisimilarity relation between Datalog goals (regular paper). In European Conference on Logics in Artificial Intelligence (JELIA), Toulouse, 26/09/2012- 28/09/2012 (, septembre 2012), L. Farinas del Cerro, A. Herzig, and J. Mengin, Eds., Springer, pp. 67–79.

YAACOUB, A. Towards an information flow in logic programming. International Journal of Computer Science Issues (IJCSI) 9, 2 (2012).

YAACOUB, A., AND AWADA, A. Inference Control On Information Flow In Logic Programming. International Journal of Computer Science: Theory and Application (IJCSTA, 2015, Vol. 3, Issue.: 1, p. 13-22.

YAACOUB, A. Flux de l’information en programmation logique Université Paul Sabatier - Toulouse III, thèse de doctorat, (2012).

LLOYD, J.W. Foundations of Logic Programming, 2nd Edition. Springer, 1987.

YAACOUB, A. AWADA, A. AND KOBEISSI, H. Information Flow in Concurrent Logic Programming. British Journal of Mathematics & Computer Science, 2015, Vol. 5, Issue.: 3, p. 367-382

STEFANO, C., AND GEORG, G., AND LETIZIA, T. What you always wanted to know about Datalog (and never dared to ask). Knowledge and Data Engineering, IEEE Transactions, 1989, Vol. 1, Issue.: 1, p. 146–166.

ULLMAN, J. Principles of Databases and Knowledge base Systems, Volume I and II. Computer Science Press, 1988.

VARDI, M. The Complexity of Relational Query Languages (Extended Abstract). Proceedings of the Fourteenth Annual ACM Symposium on Theory of Computing, 1982, p. 137–146.


  • There are currently no refbacks.

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.