---
OA_place: publisher
OA_type: gold
_id: '21133'
abstract:
- lang: eng
  text: "Data structures based on trees and tree traversals are ubiquitous in computer
    systems. Many low-level programs, including some implementations of critical systems
    like page tables and the web browser DOM, rely on generic tree-traversal functions
    that traverse tree nodes in a pre-determined order, applying a client-provided
    operation to each visited node. Developing a general approach to specifying and
    verifying such traversals is tricky since the client-provided per-node operation
    can be stateful and may potentially depend on or modify the structure of the tree
    being traversed.\r\nIn this paper, we present a recipe for (semi-)automated verification
    of such generic, stateful tree traversals. Our recipe is (a) general: it applies
    to a range of tree traversals, in particular, pre-, post- and in-order depth-first
    traversals; (b) modular: parts of a traversal’s proof can be reused in verifying
    other similar traversals; (c) expressive: using the specification of a tree traversal,
    we can verify clients that use the traversal in a variety of different ways; and
    (d) automatable: many proof obligations can be discharged automatically.\r\nAt
    the heart of our recipe is a novel use of tree zippers to represent a logical
    abstraction of the tree traversal state, and zipper transitions as an abstraction
    of traversal steps. We realize our recipe in the RefinedC framework in Rocq, which
    allows us to verify a number of different tree traversals and their clients written
    in C."
acknowledgement: We thank the anonymous reviewers for their insightful suggestions.
  This research is supported in part by generous awards from Android Security’s ASPIRE
  program and from Google Research. The third author is supported, in part, by ERC
  grant COCONUT (grant no. 101171349), funded by the European Union. Views and opinions
  expressed are however those of the author(s) only and do not necessarily reflect
  those of the European Union or the European Research Council Executive Agency. Neither
  the European Union nor the granting authority can be held responsible for them.
article_processing_charge: No
author:
- first_name: Laila
  full_name: Elbeheiry, Laila
  last_name: Elbeheiry
- first_name: Michael Joachim
  full_name: Sammler, Michael Joachim
  id: 510d3901-2a03-11ee-914d-d9ae9011f0a7
  last_name: Sammler
- first_name: Robbert
  full_name: Krebbers, Robbert
  last_name: Krebbers
- first_name: Derek
  full_name: Dreyer, Derek
  last_name: Dreyer
- first_name: Deepak
  full_name: Garg, Deepak
  last_name: Garg
citation:
  ama: 'Elbeheiry L, Sammler MJ, Krebbers R, Dreyer D, Garg D. A recipe for modular
    verification of generic tree traversals. In: <i>Proceedings of the 15th ACM SIGPLAN
    International Conference on Certified Programs and Proofs</i>. Association for
    Computing Machinery; 2026:339-352. doi:<a href="https://doi.org/10.1145/3779031.3779110">10.1145/3779031.3779110</a>'
  apa: 'Elbeheiry, L., Sammler, M. J., Krebbers, R., Dreyer, D., &#38; Garg, D. (2026).
    A recipe for modular verification of generic tree traversals. In <i>Proceedings
    of the 15th ACM SIGPLAN International Conference on Certified Programs and Proofs</i>
    (pp. 339–352). Rennes, France: Association for Computing Machinery. <a href="https://doi.org/10.1145/3779031.3779110">https://doi.org/10.1145/3779031.3779110</a>'
  chicago: Elbeheiry, Laila, Michael Joachim Sammler, Robbert Krebbers, Derek Dreyer,
    and Deepak Garg. “A Recipe for Modular Verification of Generic Tree Traversals.”
    In <i>Proceedings of the 15th ACM SIGPLAN International Conference on Certified
    Programs and Proofs</i>, 339–52. Association for Computing Machinery, 2026. <a
    href="https://doi.org/10.1145/3779031.3779110">https://doi.org/10.1145/3779031.3779110</a>.
  ieee: L. Elbeheiry, M. J. Sammler, R. Krebbers, D. Dreyer, and D. Garg, “A recipe
    for modular verification of generic tree traversals,” in <i>Proceedings of the
    15th ACM SIGPLAN International Conference on Certified Programs and Proofs</i>,
    Rennes, France, 2026, pp. 339–352.
  ista: 'Elbeheiry L, Sammler MJ, Krebbers R, Dreyer D, Garg D. 2026. A recipe for
    modular verification of generic tree traversals. Proceedings of the 15th ACM SIGPLAN
    International Conference on Certified Programs and Proofs. CPP: Conference on
    Certified Programs and Proofs, 339–352.'
  mla: Elbeheiry, Laila, et al. “A Recipe for Modular Verification of Generic Tree
    Traversals.” <i>Proceedings of the 15th ACM SIGPLAN International Conference on
    Certified Programs and Proofs</i>, Association for Computing Machinery, 2026,
    pp. 339–52, doi:<a href="https://doi.org/10.1145/3779031.3779110">10.1145/3779031.3779110</a>.
  short: L. Elbeheiry, M.J. Sammler, R. Krebbers, D. Dreyer, D. Garg, in:, Proceedings
    of the 15th ACM SIGPLAN International Conference on Certified Programs and Proofs,
    Association for Computing Machinery, 2026, pp. 339–352.
conference:
  end_date: 2026-01-13
  location: Rennes, France
  name: 'CPP: Conference on Certified Programs and Proofs'
  start_date: 2026-01-12
date_created: 2026-02-01T23:01:43Z
date_published: 2026-01-08T00:00:00Z
date_updated: 2026-02-16T08:43:24Z
day: '08'
ddc:
- '000'
department:
- _id: MiSa
doi: 10.1145/3779031.3779110
file:
- access_level: open_access
  checksum: 7df99991493e907d83a197151f378e3e
  content_type: application/pdf
  creator: dernst
  date_created: 2026-02-16T08:40:29Z
  date_updated: 2026-02-16T08:40:29Z
  file_id: '21225'
  file_name: 2026_CPP_Elbeheiry.pdf
  file_size: 811872
  relation: main_file
  success: 1
file_date_updated: 2026-02-16T08:40:29Z
fulldoi: https://doi.org/10.1145/3779031.3779110
has_accepted_license: '1'
language:
- iso: eng
month: '01'
oa: 1
oa_version: Published Version
page: 339-352
publication: Proceedings of the 15th ACM SIGPLAN International Conference on Certified
  Programs and Proofs
publication_identifier:
  isbn:
  - '9798400723414'
publication_status: published
publisher: Association for Computing Machinery
quality_controlled: '1'
scopus_import: '1'
status: public
title: A recipe for modular verification of generic tree traversals
tmp:
  image: /images/cc_by.png
  legal_code_url: https://creativecommons.org/licenses/by/4.0/legalcode
  name: Creative Commons Attribution 4.0 International Public License (CC-BY 4.0)
  short: CC BY (4.0)
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2026'
...
