Item request has been placed! ×
Item request cannot be made. ×
loading  Processing Request

A Better Approximation for Interleaved Dyck Reachability

Item request has been placed! ×
Item request cannot be made. ×
loading   Processing Request
اقرأ أكثر حفظ في قائمتي
  • المؤلفون: Kobus Conrado, Giovanna; Pavlogiannis, Andreas
  • نوع التسجيلة:
    Electronic Resource
  • الدخول الالكتروني :
    http://repository.hkust.edu.hk/ir/Record/1783.1-142202
    https://doi.org/10.1145/3652588.3663318
    http://lbdiscover.ust.hk/uresolver?url_ver=Z39.88-2004&rft_val_fmt=info:ofi/fmt:kev:mtx:journal&rfr_id=info:sid/HKUST:SPI&rft.genre=article&rft.issn=&rft.volume=&rft.issue=&rft.date=2024&rft.spage=18&rft.aulast=Conrado&rft.aufirst=Giovanna+Kobus&rft.atitle=A+Better+Approximation+for+Interleaved+Dyck+Reachability&rft.title=SOAP+2024+-+Proceedings+of+the+13th+ACM+SIGPLAN+International+Workshop+on+the+State+Of+the+Art+in+Program+Analysis%2C+Co-located+with%3A+PLDI+2024
    http://www.scopus.com/record/display.url?eid=2-s2.0-85198622688&origin=inward
    http://gateway.isiknowledge.com/gateway/Gateway.cgi?GWVersion=2&SrcAuth=LinksAMR&SrcApp=PARTNER_APP&DestLinkType=FullRecord&DestApp=WOS&KeyUT=001256719400003
  • معلومة اضافية
    • Publisher Information:
      Association for Computing Machiner 2024
    • نبذة مختصرة :
      Interleaved Dyck reachability is a standard, graph-based formulation of a plethora of static analyses that seek to be context- and field- sensitive, where each type of sensitivity is expressed via a CFL/Dyck language. Unfortunately, the problem is well-known to be undecidable in general, and as such, existing approaches resort to clever overapproximations. Recently, a mutual refinement algorithm, that iteratively considers each of the two sensitivities in isolation until a fixpoint is reached, was shown to achieve high precision. In this work we present a more precise approximation of interleaved Dyck reachability, by extending the mutual-refinement algorithm in two directions. First, we develop refined CFLs to express each type of sensitivity precisely, while simultaneously also lightly overapproximating the opposite type. Second, we apply the resulting algorithm on an on-demand basis, which effectively masks out imprecision incurred by parts of the graph that are irrelevant for the query at hand. Our experiments show that the new approach offers significantly higher precision than the vanilla mutual-refinement algorithm and other common baselines; for a particularly challenging benchmark, we report, on average, 51% of the reachable pairs compared to the most recent alternative. © 2024 Copyright held by the owner/author(s).
    • الموضوع:
      CFL Reachability; Graphs; Static Analysis; Conference paper
    • Availability:
      Open access content. Open access content
    • Note:
      English
    • Other Numbers:
      HNK oai:repository.hkust.edu.hk:1783.1-142202
      SOAP 2024: Proceedings of the 13th ACM SIGPLAN International Workshop on the State Of the Art in Program Analysis / ACM. New York, NY, United States : Association for Computing Machiner, 2024, p. 18-25
      1462194394
    • Contributing Source:
      HONG KONG UNIV OF SCI & TECH, THE
      From OAIster®, provided by the OCLC Cooperative.
    • الرقم المعرف:
      edsoai.on1462194394
HoldingsOnline