Foundations of Secure Deductive Databases

Piero A. Bonatti; Sarit Kraus; V. S. Subrahmanian

doi:10.1109/69.390247

Foundations of Secure Deductive Databases

Piero A. Bonatti, Sarit Kraus, V. S. Subrahmanian

Research output: Contribution to journal › Article › peer-review

84 Scopus citations

Abstract

In this paper, we develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no" dialogs, and “yes-no-don’t know" dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time - hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don’t know dialogs.

Original language	English (US)
Pages (from-to)	406-422
Number of pages	17
Journal	IEEE Transactions on Knowledge and Data Engineering
Volume	7
Issue number	3
DOIs	https://doi.org/10.1109/69.390247
State	Published - Jun 1995
Externally published	Yes

Funding

This work was supported by the US. Army Research Office under Grant No. DAAL-03-9243-0225, U.S. National Science Foundation Grants IRI-9109755 and IN-9123460, and Israeli Ministry of Science and Technology Grant No. 4210. We are grateful to Sushi1 Jajodia and Moshe Vardi for useful discussions. In particular, Jajodia drew our attention to [25] and Vardi to [29]. Piero Bonatti’s work was done while he was visiting the University of Maryland Institute for Advanced Computer Studies.

Keywords

Deductive databases
com-
logic programming
puter security
secure databases

ASJC Scopus subject areas

Information Systems
Computer Science Applications
Computational Theory and Mathematics

Access to Document

10.1109/69.390247

Cite this

@article{dadbfae7630347ae8de19e0e7f0e06c6,

title = "Foundations of Secure Deductive Databases",

abstract = "In this paper, we develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no{"} dialogs, and “yes-no-don{\textquoteright}t know{"} dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time - hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don{\textquoteright}t know dialogs.",

keywords = "Deductive databases, com-, logic programming, puter security, secure databases",

author = "Bonatti, {Piero A.} and Sarit Kraus and Subrahmanian, {V. S.}",

note = "Funding Information: This work was supported by the US. Army Research Office under Grant No. DAAL-03-9243-0225, U.S. National Science Foundation Grants IRI-9109755 and IN-9123460, and Israeli Ministry of Science and Technology Grant No. 4210. We are grateful to Sushi1 Jajodia and Moshe Vardi for useful discussions. In particular, Jajodia drew our attention to [25] and Vardi to [29]. Piero Bonatti{\textquoteright}s work was done while he was visiting the University of Maryland Institute for Advanced Computer Studies.",

year = "1995",

month = jun,

doi = "10.1109/69.390247",

language = "English (US)",

volume = "7",

pages = "406--422",

journal = "IEEE Transactions on Knowledge and Data Engineering",

issn = "1041-4347",

publisher = "IEEE Computer Society",

number = "3",

}

TY - JOUR

T1 - Foundations of Secure Deductive Databases

AU - Bonatti, Piero A.

AU - Kraus, Sarit

AU - Subrahmanian, V. S.

N1 - Funding Information: This work was supported by the US. Army Research Office under Grant No. DAAL-03-9243-0225, U.S. National Science Foundation Grants IRI-9109755 and IN-9123460, and Israeli Ministry of Science and Technology Grant No. 4210. We are grateful to Sushi1 Jajodia and Moshe Vardi for useful discussions. In particular, Jajodia drew our attention to [25] and Vardi to [29]. Piero Bonatti’s work was done while he was visiting the University of Maryland Institute for Advanced Computer Studies.

PY - 1995/6

Y1 - 1995/6

N2 - In this paper, we develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no" dialogs, and “yes-no-don’t know" dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time - hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don’t know dialogs.

AB - In this paper, we develop a formal logical foundation for secure deductive databases. This logical foundation is based on an extended logic involving several modal operators. We develop two models of interaction between the user and the database called “yes-no" dialogs, and “yes-no-don’t know" dialogs. Both dialog frameworks allow the database to lie to the user. We develop an algorithm for answering queries using yes-no dialogs and prove that secure query processing using yes-no dialogs is NP-complete. Consequently, the degree of computational intractability of query processing with yes-no dialogs is no worse than for ordinary databases. Furthermore, the algorithm is maximally cooperative to user in the sense that lying is resorted to only when absolutely necessary. For Horn databases, we show that secure query processing can be achieved in linear time - hence, this is no more intractable than the situation in ordinary databases. Finally, we identify necessary and sufficient conditions for the database to be able to preserve security. Similar results are also obtained for yes-no-don’t know dialogs.

KW - Deductive databases

KW - com-

KW - logic programming

KW - puter security

KW - secure databases

UR - http://www.scopus.com/inward/record.url?scp=0029324246&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0029324246&partnerID=8YFLogxK

U2 - 10.1109/69.390247

DO - 10.1109/69.390247

M3 - Article

AN - SCOPUS:0029324246

SN - 1041-4347

VL - 7

SP - 406

EP - 422

JO - IEEE Transactions on Knowledge and Data Engineering

JF - IEEE Transactions on Knowledge and Data Engineering

IS - 3

ER -

Foundations of Secure Deductive Databases

Abstract

Funding

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this