Collaborative planning with confidentiality. (English) Zbl 1229.90072
This article proposes a formal model for collaboration which includes concerns of confidentiality between the agents. The authors begin with an introductory section presenting the existing literature and relevant elements from the area of artificial intelligence (AI). The second section proceeds to describe action systems which are formal AI ways to describe the environment and the actions that are permitted to the agents to achieve a desired goal. The third section moves to consider planning, which is modeled as an element of a state-transition system. This is followed by a presentation of a formal approach to data confidentiality policies and the ways they can be represented in the model. The logical structure of the proposed collaborative planning with confidentiality concerns model is presented in the fifth section, where several of its properties are studied. The sixth section investigates the complexity and completeness of the proposed model and the paper concludes with a section on suggested future work and a list of relevant references.
Reviewer: Efstratios Rappos (Aubonne)
MSC:
| 90B70 | Theory of organizations, manpower planning in operations research |
| 68T20 | Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) |
| 03B80 | Other applications of logic |
References:
| [1] | Alur, R., Černý, P., Chaudhuri, S.: Model checking on trees with path equivalences. In: TACAS 2007, pp. 664–678. Springer (2007) · Zbl 1186.68273 |
| [2] | Alur, R., Černý, P., Zdancewic, S.: Preserving secrecy under refinement. In: ICALP ’06: Proceedings (Part II) of the 33rd International Colloquium on Automata, Languages and Programming, pp. 107–118. Springer (2006) · Zbl 1133.94307 |
| [3] | Ashley, P., Hada, S., Karjoth, G., Powers, C., Schunter, M.:Enterprise privacy authorization language (EPAL 1.2) (2003). http://www.zurich.ibm.com/security/enterprise-privacy/epal/Specification/index.html |
| [4] | Barh, A., Mitchell, J.C., Datta, A., Sundaram, S.: Privacy and utility in business processes. In: 20th IEEE Computer Security Foundations Symposium (CSF 20). Venice, Italy (2007) |
| [5] | Barth, A., Datta, A., Mitchell, J.C., Nissenbaum, H.: Privacy and conextual integrity: framework and applications. In: 27th IEEE Symposium on Security and Privacy (2006) |
| [6] | Bibel, W.: A deductive solution for plan generation. New Gener. Comput. 4(2), 115–132 (1986) · Zbl 0624.68079 · doi:10.1007/BF03037438 |
| [7] | Cervesato, I., Durgin, N., Kanovich, M., Scedrov, A.: Interpreting strands in linear logic. In: Veith, H., Heintze, N., Clark, E. (eds.) 2000 Workshop on Formal Methods and Computer Security–FMCS’00. Chicago, IL (2000) |
| [8] | Cervesato, I., Scedrov, A.: Relating state-based and process-based concurrency through linear logic. In: de Queiroz, R. (ed.) Thirteenth Workshop on Logic, Language, Information and Computation–WoLLIC’06, Stanford, CA, 18–21 July, pp. 145–176. Elsevier ENTCS 165 (2006) · Zbl 1262.68136 |
| [9] | Cervesato, I., Scedrov, A.: Relating state-based and process-based concurrency through linear logic (full-version). Inf. Comput. 207(10), 1044–1077 (2009) · Zbl 1181.68168 · doi:10.1016/j.ic.2008.11.006 |
| [10] | Chapman, D.: Planning for conjunctive goals. Artif. Intell. 32(3), 333–377 (1987) · Zbl 0642.68171 · doi:10.1016/0004-3702(87)90092-0 |
| [11] | Dolev, D., Yao, A.: On the security of public key protocols. IEEE Trans. Inf. Theory 29(2), 198–208 (1983) · Zbl 0502.94005 · doi:10.1109/TIT.1983.1056650 |
| [12] | Durgin, N., Lincoln, P., Mitchell, J., Scedrov, A.: Multiset rewriting and the complexity of bounded security protocols. J. Comput. Secur. 12(2), 247–311 (2004) |
| [13] | Garg, D., Bauer, L., Bowers, K.D., Pfenning, F., Reiter, M.K.: A linear logic of authorization and knowledge. In: Proceedings of the 11th European Symposium on Research in Computer Science (ESORICS’06). Springer Lecture Notes in Computer Science, vol. 4189, pp. 297–312. Springer-Verlag (2006) |
| [14] | Garg, D., Pfenning, F.: Non-interference in constructive authorization logic. In: Proc. of the IEEE Computer Security Foundations Workshop (CSFW), pp. 283–296 (2006) |
| [15] | Gehlot, V., Gunter, C.: Normal process representatives. In: Proc. of the Fifth Annual IEEE Symposium on Logic in Computer Science, pp. 200–207. Philadelphia, PA (1990) |
| [16] | Girard, J.-Y.: Linear logic. Theor. Comp. Sci. 50(1), 1–102 (1987) · Zbl 0625.03037 · doi:10.1016/0304-3975(87)90045-4 |
| [17] | Girard, J.-Y.: Linear logic: Its syntax and semantics. In: Girard, J.-Y., Lafont, Y., Regnier, L. (eds.) Advances in Linear Logic. London Mathematical Society Lecture Notes, vol. 222, pp. 1–42. Cambridge University Press (1995) · Zbl 0828.03003 |
| [18] | Goguen, J.A., Meseguer, J.: Security policies and security models. In: IEEE Symposium on Security and Privacy, pp. 11–20 (1982) |
| [19] | Greenstadt, R., Pierce, J.P., Tambe, M.: Analysis of privacy loss in distributed constraint optimization. In: 21st Conference on Artificial Intelligence (AAAI). Boston, MA (2006) |
| [20] | Greenstadt, R., Smith, M.D.: Collaborative scheduling: threats and promises. In: Fifth Annual Workshop on Economics and Information Security. Cambridge, England (2006) |
| [21] | Hopcroft, J.E., Motwani, R., Ullman, J.D.: Introduction to Automata Theory, Languages, and Computation. Addison-Wesley Longman Publishing Co., Inc., Boston, MA (2001) · Zbl 0980.68066 |
| [22] | Ives, Z.G., Khandelwal, N., Kapur, A., Cakir, M.: ORCHESTRA: Rapid, collaborative sharing of dynamic data. In: Conference on Innovative Data Systems Research (CIDR), pp. 107–118 (2005) |
| [23] | Jones, N.D., Landweber, L.H., Lien, Y.E.: Complexity of some problems in Petri nets. Theor. Comp. Sci. 4(3), 277–299 (1977) · Zbl 0357.68048 · doi:10.1016/0304-3975(77)90014-7 |
| [24] | Kanovich, M., Rowe, P., Scedrov, A.: Collaborative planning with privacy. In: 20th IEEE Computer Security Foundations Symposium (CSF 20). Venice, Italy (2007) · Zbl 1229.90072 |
| [25] | Kanovich, M., Rowe, P., Scedrov, A.: Policy compliance in collaborative systems. In: 22nd IEEE Computer Security Foundations Symposium (CSF22), pp. 218–233. Port Jefferson, NY (2009) |
| [26] | Kanovich, M., Vauzeilles, J.: The classical AI planning problems in the mirror of Horn linear logic: semantics, expressibility, complexity. Math. Struct. Comput. Sci. 11(6), 689–716 (2001) · Zbl 0994.68139 · doi:10.1017/S0960129501003413 |
| [27] | Kanovich, M.I.: Horn programming in linear logic is NP-complete. In: Proc. 7-th Annual IEEE Syposium on Logic in Computer Science, Santa Cruz, pp. 200–210 (1992) |
| [28] | Kanovich, M.I.: The complexity of Horn fragments of linear logic. Ann. Pure Appl. Logic 69, 195–241 (1994) · Zbl 0812.03007 · doi:10.1016/0168-0072(94)90085-X |
| [29] | Kanovich, M.I.: Linear logic as a logic of computations. Ann. Pure Appl. Logic 67, 183–212 (1994) · Zbl 0804.03004 · doi:10.1016/0168-0072(94)90011-6 |
| [30] | Kanovich, M.I.: The direct simulation of Minsky machines in linear logic. In: Girard, J.-Y., Lafont, Y., Regnier, L. (eds.) Advances in Linear Logic. London Mathematical Society Lecture Notes, vol. 222, pp. 123–145 (1995) · Zbl 0826.03018 |
| [31] | Kanovich, M.I.: Petri nets, Horn programs, linear logic and vector games. Ann. Pure Appl. Logic 75(1-2), 107–135 (1995) · Zbl 0829.03007 · doi:10.1016/0168-0072(94)00060-G |
| [32] | Li, M., Vitanyi, P.: An introduction to Kolmogorov complexity and its applications. Springer, New York (1997) |
| [33] | Lincoln, P.D., Shankar, N.: Proof search in first-order linear logic and other cut-free sequent calculi. In: Ninth Annual Symposium on Logic in Computer Science (Paris, France), pp. 282–291. IEEE Computer Society Press (1994) |
| [34] | Masseron, M., Tollu, C., Vauzeilles, J.: Generating plans in linear logic I: actions as proofs. Theor. Comp. Sci. 113(2), 349–370 (1993) · Zbl 0787.03006 · doi:10.1016/0304-3975(93)90007-G |
| [35] | Mayr, E.W.: An algorithm for the general Petri net reachability problem. SIAM J. Comput. 13(3), 441–460 (1984) · Zbl 0563.68057 · doi:10.1137/0213029 |
| [36] | McDermott, D., Hendler, J.: Planning: what it is, what it could be, An introduction to the special issue on planning and scheduling. Artif. Intell. 76, 1–16 (1995) |
| [37] | McLean, J.: Security models. In: Marciniak, J. (ed.) Encyclopedia of Software Engineering. Wiley (1994) |
| [38] | Meseguer, J.: Conditional rewriting logic as a unified model of concurrency. In: Selected Papers of the Second Workshop on Concurrency and Compositionality, pp. 73–155. Elsevier Science Publishers Ltd. Essex (1992) · Zbl 0758.68043 |
| [39] | Myers, A.C., Sabelfeld, A., Zdancewic, S.: Enforcing robust declassification and qualified robustness. J. Comput. Secur. 14(2), 157–196 (2006). Extended abstract in CSFW, pp. 172–186 (2004) |
| [40] | Nilsson, N.J.: Principles of Artificial Intelligence. Springer, Berlin (1980) · Zbl 0422.68039 |
| [41] | Papadimitriou, C.: Computational Complexity. Addison-Wesley Publishing Company, Inc., Reading, MA (1994) · Zbl 0833.68049 |
| [42] | Reagle, J., Cranor, L.F.: The platform for privacy preferences. Commun. ACM 42(2), 48–55 (1999) · doi:10.1145/293411.293455 |
| [43] | Reynolds, J.C.: Syntactic control of interference. In: Symposium on Principles of Programming Languages (POPL), pp. 39–46 (1978) |
| [44] | Rowe, P.: Policy Compliance, Confidentiality and Complexity in Collaborative Systems. PhD thesis, University of Pennsylvania (2009) |
| [45] | Savitch, W.J., Relationship between nondeterministic and deterministic tape classes. J. Comput. Syst. Sci. 4, 177–192 (1970) · Zbl 0188.33502 · doi:10.1016/S0022-0000(70)80006-X |
| [46] | Scedrov, A.: Linear logic and computation: A survey. In: Schwichtenberg, H. (ed.) Proof and Computation, Proceedings Marktoberdorf Summer School 1993, pp. 281–298. NATO Advanced Science Institutes, Series F, Springer-Verlag, Berlin (1994) |
| [47] | Taylor, N.E., Ives, Z.G.: Reconciling while tolerating disagreement in collaborative data sharing. In: ACM SIGMOD Conference on Management of Data, pp. 13–24 (2006) |
| [48] | Wiederhold, G., Bilello, M., Sarathy, V., Qian, X.: Protecting collaboration. In: Proc. 19th NIST-NCSC National Information Systems Security Conference, pp. 561–569 (1996) |
| [49] | Zdancewic, S., Myers, A.C.: Robust declassification. In: Proc. 14th IEEE Computer Securtiy Foundations Workshop (CSFW), pp. 15–23 (2001) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
