하이퍼 프로퍼티

컴퓨터 과학에서, 하이퍼 속성은 컴퓨터 시스템의 속성을 설명하기 위한 형식주의입니다.하이퍼 속성은 안전 및 활성 속성을 일반화하고 비간섭 및 관찰 결정론과 같은 속성을 표현할 수 있습니다.

정의들

추적 및 시스템

하이퍼 속성은 계산 시스템의 트레이스 측면에서 정의됩니다.추적은 상태의 시퀀스이고 시스템은 추적의 집합입니다.직관적으로, 프로그램은 모든 입력이 주어지면 가능한 모든 실행 추적 세트에 해당합니다.공식적으로, 일련의 상태 ${displaystyle$ \ $Sigma}$ 에 $\Sigma$ 대한 추적 $\Phi \triangleq \Sigma ^{\omega }$ 은 $\Phi \triangleq \Sigma ^{\omega }$ $Δ$ Δ Δ \ displaystyle $\Phi \triangleq$ \Sigma ^{\omega $\Phi \triangleq \Sigma ^{\omega }$ 입니다.

이 표현은 레이블이 지정된 전환^[1] 시스템 및 상태 ^[2]기계를 포함한 여러 계산 모델을 포함할 수 있을 정도로 충분히 표현적입니다.

하이퍼프로퍼티

추적 속성은 추적의 집합입니다.안전 및 활성 속성은 추적 속성입니다.공식적으로 추적 속성은 P $)$ 의 $\mathbb {P} (\Phi )$ 이며, $\mathbb {P}$ 서 P $({$ 는 $\mathbb {P}$ $\mathbb {P}$ $멱집합$ 연산자입니다.초특성은 추적 특성의 집합, 즉 P $\mathbb {P} (\mathbb {P} (\Phi ))$ 의 $\mathbb {P} (\mathbb {P} (\Phi ))$ 입니다 $.$ \ $displaystyle \mathbb {P}(\mathbb {P}(\Phi$

추적 속성은 안전 속성(직관적으로 "나쁜 일이 발생하지 않도록 보장하는 속성")과 활성 속성("좋은 일이 발생합니다")으로 나눌 수 있으며, 모든 추적 속성은 안전 속성과 활성 ^[3]속성의 교차점입니다.유사하게, 하이퍼 속성은 하이퍼 안전 및 하이퍼 라이브 하이퍼 속성으로 나눌 수 있으며, 모든 하이퍼 속성은 안전 하이퍼 속성과 활성 하이퍼 ^[4]속성의 교차점입니다.

${displaystyle$ k} - 안전 $k$ 속성은 안전 하이퍼 속성이므로 속성을 위반할 때마다 최대 ${displaystyle$ k}개의 $k$ ^[5]추적을 통해 확인할 수 있습니다.

예

모든 안전 속성은 동일한 ^[6]조건을 나타내는 1-안전 하이퍼 속성으로 들어올릴 수 있습니다.
${displaystyle$ k $}$ - 안전 하이퍼 $k$ 속성:
- $k=1$ $=$ {{ $displaystyle k=$ 1}( $k=1$ 안전 속성의 정의):
  - false, 빈 집합을 포함하는 집합으로 정의됩니다. $\mathbf {false} \triangleq \{\emptyset \}$ 으로 $\mathbf {false} \triangleq \{\emptyset \}$ { ∅ $}$ { \ $displaystyle \mathbf {false}$ \ $triangleq \{\emptyset$ 이 하이퍼 속성은 어떤 ^[7]시스템에서도 충족되지 않습니다.
  - true, 모든 추적의 집합으로 정의됩니다. $\mathbf {true} \triangleq \Phi$ 으로 $≜$ \ $displaystyle \mathbf {true}$ \ $triangleq \Phi$ 이 $\mathbf {true} \triangleq \Phi$ 속성은 모든 시스템에서 ^[8]충족됩니다.
  - 접근통제^[9]
- $k=2$ $=$ $k=2$ {{ $displaystyle$ k= $2$ :
  - 단조로움^[10]
  - 주입률^[10]
  - 대칭, 반대칭 및 비대칭^[10]
  - 관측 결정론^[11]
  - 비간섭
- $k=3$ $k=3$
  - 과도성^[10]
- $k=4$ $k=4$
  - 연상^[10]

특성.

초특성은 정확하게 $\mathbb {P} (\mathbb {P} (\Phi ))$ P $\mathbb {P} (\mathbb {P} (\Phi ))$ ( $Δ))$ 의 원소이기 때문에 (\ $mathbb {P}(\Phi$ 교집합과 합집합 하에서 닫힙니다.

추적 속성에 대한 표준 토폴로지의 하위 Vietoris 토폴로지는 하이퍼 ^[12]속성 집합에 대한 토폴로지를 생성합니다.

적용들

여러 프로그램^[10]^[13] 논리(가장 유명한 것은LTL^[14]) 및 모델 검사^[15]^[16] 알고리즘은 시스템이 하이퍼 속성을 준수하는지 확인하기 위해 개발되었습니다.

레퍼런스

메모들

^ Clarkson & Schneider, p. 23: "레이블된 전이 시스템 [...]은 일련의 추적으로 인코딩될 수 있습니다." sfn 오류: 대상 없음: CITEREFClarkson Schneider (도움말)
^ Clarkson & Schneider, p. 25: "상태 기계 M [...]은 추적 세트로 인코딩될 수 있습니다." sfn 오류: 대상 없음: CITEREFClarkson Schneider (도움말)
^ Alpern, Bowen; Schneider, Fred B. (1985-10-07). "Defining liveness". Information Processing Letters. 21 (4): 181–185. doi:10.1016/0020-0190(85)90056-0. ISSN 0020-0190.
^ Clarkson & Schneider, 페이지 21. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)
^ Finkbeiner, Bernd; Haas, Lennart; Torfah, Hazem (June 2019). "Canonical Representations of k-Safety Hyperproperties". 2019 IEEE 32nd Computer Security Foundations Symposium (CSF): 17–1714. doi:10.1109/CSF.2019.00009. ISBN 978-1-7281-1407-1. S2CID 201848133.
^ Clarkson & Schneider, 페이지 11: "안전 속성에서 안전 하이퍼 속성으로 상승". sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)
^ Clarkson & Schneider, p. 15: "\{\emptyset\}로 정의되는 하이퍼 속성 false는 하이퍼 안전이지만 하이퍼 라이브는 아닙니다."
^ Clarkson & Schneider, 페이지 44. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)
^ Clarkson & Schneider. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)
^ ^a ^b ^c ^d ^e ^f Sousa & Dillig.sfn 오류: 대상 없음: CITEREFsous Dillig (도움말)
^ Clarkson & Schneider, p. 13: "관측 결정론 OD(2.6)는 2-안전 특성으로 표현될 수 없지만, 2-안전 초특성입니다." sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)
^ Clarkson & Schneider, 페이지 19. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)
^ Dardinier, Thibault; Müller, Peter (2023-01-24). "Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties (extended version)". arXiv:2301.10037 [cs.LO].
^ Clarkson, Michael R.; Finkbeiner, Bernd; Koleini, Masoud; Micinski, Kristopher K.; Rabe, Markus N.; Sánchez, César (2014). Abadi, Martín; Kremer, Steve (eds.). "Temporal Logics for Hyperproperties". Principles of Security and Trust. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 8414: 265–284. doi:10.1007/978-3-642-54792-8_15. ISBN 978-3-642-54792-8. S2CID 8938993.
^ Finkbeiner, Bernd; Rabe, Markus N.; Sánchez, César (2015). Kroening, Daniel; Păsăreanu, Corina S. (eds.). "Algorithms for Model Checking HyperLTL and HyperCTL$^*$". Computer Aided Verification. Lecture Notes in Computer Science. Cham: Springer International Publishing. 9206: 30–48. doi:10.1007/978-3-319-21690-4_3. ISBN 978-3-319-21690-4.
^ Hsu, Tzu-Han; Sánchez, César; Bonakdarpour, Borzoo (2021). Groote, Jan Friso; Larsen, Kim Guldstrand (eds.). "Bounded Model Checking for Hyperproperties". Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Cham: Springer International Publishing. 12651: 94–112. doi:10.1007/978-3-030-72016-2_6. ISBN 978-3-030-72016-2. PMC 7979203.

원천

Clarkson, Michael R.; Schneider, Fred B. (2010-09-20). Sabelfeld, Andrei (ed.). "Hyperproperties". Journal of Computer Security. 18 (6): 1157–1210. doi:10.3233/JCS-2009-0393. S2CID 218604768.
Sousa, Marcelo; Dillig, Isil (2016-06-02). "Cartesian hoare logic for verifying k-safety properties". Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation. PLDI '16. New York, NY, USA: Association for Computing Machinery: 57–69. doi:10.1145/2908080.2908092. ISBN 978-1-4503-4261-2. S2CID 17433405.

[FOOTNOTEClarksonSchneiderp._23:_"A_labeled_transition_system_[...]_can_be_encoded_as_a_set_of_traces."-1] Clarkson & Schneider, p. 23: "레이블된 전이 시스템 [...]은 일련의 추적으로 인코딩될 수 있습니다." sfn 오류: 대상 없음: CITEREFClarkson Schneider (도움말)

[FOOTNOTEClarksonSchneiderp._25:_"A_state_machine_M_[...]_can_be_encoded_as_a_set_of_traces."-2] Clarkson & Schneider, p. 25: "상태 기계 M [...]은 추적 세트로 인코딩될 수 있습니다." sfn 오류: 대상 없음: CITEREFClarkson Schneider (도움말)

[3] Alpern, Bowen; Schneider, Fred B. (1985-10-07). "Defining liveness". Information Processing Letters. 21 (4): 181–185. doi:10.1016/0020-0190(85)90056-0. ISSN 0020-0190.

[FOOTNOTEClarksonSchneider21-4] Clarkson & Schneider, 페이지 21. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)

[5] Finkbeiner, Bernd; Haas, Lennart; Torfah, Hazem (June 2019). "Canonical Representations of k-Safety Hyperproperties". 2019 IEEE 32nd Computer Security Foundations Symposium (CSF): 17–1714. doi:10.1109/CSF.2019.00009. ISBN 978-1-7281-1407-1. S2CID 201848133.

[FOOTNOTEClarksonSchneiderp._11:_"Safety_properties_lift_to_safety_hyperproperties"-6] Clarkson & Schneider, 페이지 11: "안전 속성에서 안전 하이퍼 속성으로 상승". sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)

[FOOTNOTEClarksonSchneiderp._15:_"The_hyperproperty_false,_defined_as_\{\emptyset\},_is_hypersafety_but_not_hyperliveness".-7] Clarkson & Schneider, p. 15: "\{\emptyset\}로 정의되는 하이퍼 속성 false는 하이퍼 안전이지만 하이퍼 라이브는 아닙니다."

[FOOTNOTEClarksonSchneider44-8] Clarkson & Schneider, 페이지 44. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)

[FOOTNOTEClarksonSchneider-9] Clarkson & Schneider. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)

[FOOTNOTESousaDillig-10] ^ ^a ^b ^c ^d ^e ^f Sousa & Dillig.sfn 오류: 대상 없음: CITEREFsous Dillig (도움말)

[FOOTNOTEClarksonSchneiderp._13:_"observational_determinism_OD_(2.6)_cannot_be_expressed_as_a_2-safety_property,_but_it_is_a_2-safety_hyperproperty"-11] Clarkson & Schneider, p. 13: "관측 결정론 OD(2.6)는 2-안전 특성으로 표현될 수 없지만, 2-안전 초특성입니다." sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)

[FOOTNOTEClarksonSchneider19-12] Clarkson & Schneider, 페이지 19. sfn 오류: 대상 없음: CITEREFClarkson Schneider(도움말)

[13] Dardinier, Thibault; Müller, Peter (2023-01-24). "Hyper Hoare Logic: (Dis-)Proving Program Hyperproperties (extended version)". arXiv:2301.10037 [cs.LO].

[14] Clarkson, Michael R.; Finkbeiner, Bernd; Koleini, Masoud; Micinski, Kristopher K.; Rabe, Markus N.; Sánchez, César (2014). Abadi, Martín; Kremer, Steve (eds.). "Temporal Logics for Hyperproperties". Principles of Security and Trust. Lecture Notes in Computer Science. Berlin, Heidelberg: Springer. 8414: 265–284. doi:10.1007/978-3-642-54792-8_15. ISBN 978-3-642-54792-8. S2CID 8938993.

[15] Finkbeiner, Bernd; Rabe, Markus N.; Sánchez, César (2015). Kroening, Daniel; Păsăreanu, Corina S. (eds.). "Algorithms for Model Checking HyperLTL and HyperCTL$^*$". Computer Aided Verification. Lecture Notes in Computer Science. Cham: Springer International Publishing. 9206: 30–48. doi:10.1007/978-3-319-21690-4_3. ISBN 978-3-319-21690-4.

[16] Hsu, Tzu-Han; Sánchez, César; Bonakdarpour, Borzoo (2021). Groote, Jan Friso; Larsen, Kim Guldstrand (eds.). "Bounded Model Checking for Hyperproperties". Tools and Algorithms for the Construction and Analysis of Systems. Lecture Notes in Computer Science. Cham: Springer International Publishing. 12651: 94–112. doi:10.1007/978-3-030-72016-2_6. ISBN 978-3-030-72016-2. PMC 7979203.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

Search

하이퍼 프로퍼티

네임스페이스

더

목차

정의들

추적 및 시스템

하이퍼프로퍼티

예

특성.

적용들

레퍼런스

메모들

원천