Channel Capacity of Concurrent Probabilistic Programs
Programs are under continuous attack for disclosing secret information, and defending against these attacks is becoming increasingly vital. An attractive approach for protection is to measure the amount of secret information that might leak to attackers. A fundamental issue in computing information...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2019-09-01
|
| Series: | Entropy |
| Subjects: | |
| Online Access: | https://www.mdpi.com/1099-4300/21/9/885 |
| _version_ | 1818037993513943040 |
|---|---|
| author | Khayyam Salehi Jaber Karimpour Habib Izadkhah Ayaz Isazadeh |
| author_facet | Khayyam Salehi Jaber Karimpour Habib Izadkhah Ayaz Isazadeh |
| author_sort | Khayyam Salehi |
| collection | DOAJ |
| description | Programs are under continuous attack for disclosing secret information, and defending against these attacks is becoming increasingly vital. An attractive approach for protection is to measure the amount of secret information that might leak to attackers. A fundamental issue in computing information leakage is that given a program and attackers with various knowledge of the secret information, what is the maximum amount of leakage of the program? This is called channel capacity. In this paper, two notions of capacity are defined for concurrent probabilistic programs using information theory. These definitions consider intermediate leakage and the scheduler effect. These capacities are computed by a constrained nonlinear optimization problem. Therefore, an evolutionary algorithm is proposed to compute the capacities. Single preference voting and dining cryptographers protocols are analyzed as case studies to show how the proposed approach can automatically compute the capacities. The results demonstrate that there are attackers who can learn the whole secret of both the single preference protocol and dining cryptographers protocol. The proposed evolutionary algorithm is a general approach for computing any type of capacity in any kind of program. |
| first_indexed | 2024-12-10T07:35:40Z |
| format | Article |
| id | doaj.art-cc171d9395ca4d44a433cd9a333dd095 |
| institution | Directory Open Access Journal |
| issn | 1099-4300 |
| language | English |
| last_indexed | 2024-12-10T07:35:40Z |
| publishDate | 2019-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Entropy |
| spelling | doaj.art-cc171d9395ca4d44a433cd9a333dd0952022-12-22T01:57:27ZengMDPI AGEntropy1099-43002019-09-0121988510.3390/e21090885e21090885Channel Capacity of Concurrent Probabilistic ProgramsKhayyam Salehi0Jaber Karimpour1Habib Izadkhah2Ayaz Isazadeh3Department of Computer Science, University of Tabriz, Tabriz 51666-16471, IranDepartment of Computer Science, University of Tabriz, Tabriz 51666-16471, IranDepartment of Computer Science, University of Tabriz, Tabriz 51666-16471, IranDepartment of Computer Science, University of Tabriz, Tabriz 51666-16471, IranPrograms are under continuous attack for disclosing secret information, and defending against these attacks is becoming increasingly vital. An attractive approach for protection is to measure the amount of secret information that might leak to attackers. A fundamental issue in computing information leakage is that given a program and attackers with various knowledge of the secret information, what is the maximum amount of leakage of the program? This is called channel capacity. In this paper, two notions of capacity are defined for concurrent probabilistic programs using information theory. These definitions consider intermediate leakage and the scheduler effect. These capacities are computed by a constrained nonlinear optimization problem. Therefore, an evolutionary algorithm is proposed to compute the capacities. Single preference voting and dining cryptographers protocols are analyzed as case studies to show how the proposed approach can automatically compute the capacities. The results demonstrate that there are attackers who can learn the whole secret of both the single preference protocol and dining cryptographers protocol. The proposed evolutionary algorithm is a general approach for computing any type of capacity in any kind of program.https://www.mdpi.com/1099-4300/21/9/885channel capacityinformation theoryevolutionary algorithmsquantitative information flowconcurrent probabilistic programs |
| spellingShingle | Khayyam Salehi Jaber Karimpour Habib Izadkhah Ayaz Isazadeh Channel Capacity of Concurrent Probabilistic Programs Entropy channel capacity information theory evolutionary algorithms quantitative information flow concurrent probabilistic programs |
| title | Channel Capacity of Concurrent Probabilistic Programs |
| title_full | Channel Capacity of Concurrent Probabilistic Programs |
| title_fullStr | Channel Capacity of Concurrent Probabilistic Programs |
| title_full_unstemmed | Channel Capacity of Concurrent Probabilistic Programs |
| title_short | Channel Capacity of Concurrent Probabilistic Programs |
| title_sort | channel capacity of concurrent probabilistic programs |
| topic | channel capacity information theory evolutionary algorithms quantitative information flow concurrent probabilistic programs |
| url | https://www.mdpi.com/1099-4300/21/9/885 |
| work_keys_str_mv | AT khayyamsalehi channelcapacityofconcurrentprobabilisticprograms AT jaberkarimpour channelcapacityofconcurrentprobabilisticprograms AT habibizadkhah channelcapacityofconcurrentprobabilisticprograms AT ayazisazadeh channelcapacityofconcurrentprobabilisticprograms |