A Formal Proof of a Unix Path Resolution Algorithm

Ran Chen 1, 2, 3 Martin Clochard 2, 3 Claude Marché 2, 3
2 TOCCATA - Certified Programs, Certified Tools, Certified Floating-Point Computations
LRI - Laboratoire de Recherche en Informatique, UP11 - Université Paris-Sud - Paris 11, Inria Saclay - Ile de France, CNRS - Centre National de la Recherche Scientifique : UMR8623
Abstract : In the context of file systems like those of Unix, path resolution is the operation that given a character string denoting an access path, determines the target object (file, directory, etc.) designated by this path. This operation is not trivial because of the presence of symbolic links. Indeed, the presence of such links may induce infinite loops. In this report we consider a path resolution algorithm that always terminate. We propose a formal specifi- cation of path resolution and we formally prove that our algorithm terminates on any input, and is correct and complete.
Document type :
Reports
Liste complète des métadonnées

https://hal.inria.fr/hal-01406848
Contributor : Claude Marché <>
Submitted on : Thursday, December 1, 2016 - 3:52:40 PM
Last modification on : Thursday, April 5, 2018 - 12:30:22 PM
Document(s) archivé(s) le : Tuesday, March 21, 2017 - 11:02:56 AM

File

RR-8987.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01406848, version 1

Citation

Ran Chen, Martin Clochard, Claude Marché. A Formal Proof of a Unix Path Resolution Algorithm. [Research Report] RR-8987, Inria. 2016, pp.27. ⟨hal-01406848⟩

Share

Metrics

Record views

547

Files downloads

421