臺灣博碩士論文加值系統

此篇論文應用機率近似模型學習演算法學習多樣性自動機。該演算法會產生目標軟體之多樣性自動機模型，並將其應用於量化分析。使用產生之多樣性自動機模型，我們設計了一系列演算法可以預測軟體量化分析目標軟體的最大值與平均值等特性。此外，我們修改該演算法，使其在輸入字母數量並非固定時也可以通用。在此片論文中我們實際測試了五種不同類型的軟體，實驗證明我們預測的結果與暴力法算得之結果相當接近，足以證明此演算法可以產生一些傳統難以預測的數據，並具有相當高的可信度。

In this paper, we apply a probably approximately correct (PAC) learning algorithm for multiplicity automata which can generate a quantitative model of target system behaviors with a statistical guarantee. By using the generated multiplicity automata model, we apply two analysis algorithms to estimate the minimum, maximum and average values of system behaviors. Also, we demonstrate how to apply the learning algorithm when the alphabet symbol size is not fixed. The result of the experiment is encouraging; Our approach made the estimation which is as precise as the exact reference answer obtains by a brute force enumeration.

口試委員會審定書 #
誌謝 i
中文摘要 ii
ABSTRACT iii
CONTENTS iv
LIST OF FIGURES vii
LIST OF TABLES viii
Chapter 1 Introduction 1
1.1 Motivation 1
1.2 Related Work 3
1.3 Contribution 4
Chapter 2 Preliminaries 5
2.1 Multiplicity Automata 5
2.2 Hankel Matrix 6
Chapter 3 Learning Algorithm of MA 7
3.1 PAC Learning 7
Chapter 4 Overview 10
Chapter 5 Analyzing Properties of MA 12
5.1 Computing the min. of 13
5.2 Computing the average of 14
Chapter 6 Optimizations 15
6.1 Learning the alphabet symbols incrementally 15
6.2 Double check the learned min./max. value 16
Chapter 7 Running Example: Calculator 17
Chapter 8 Calculator Experiment 21
8.1 Calculator 21
8.2 Considerations on the choice of distribution 22
8.3 Incremental alphabet refinement 23
8.4 Distribution of the execution time 23
Chapter 9 Operating System Scheduling Experiment 25
Chapter 10 Missionaries and Cannibals Experiment 26
Chapter 11 Amount of Data Transmission in a Website 28
Summary 29
REFERENCE 30

1. Android Studio: the Monkey tester. https://developer.android.com/studio/ test/monkey.html (2017) Accessed: 2017-01-08.
2. Angluin, D.: Learning regular sets from queries and counterexamples. Information and Computation 75(2) (1987) 87–106
3. Angluin, D.: Queries and concept learning. Machine Learning 2(4) (1988) 319–342
4. Beimel, A., Bergadano, F., Bshouty, N.H., Kushilevitz, E., Varricchio, S.: Learning functions represented as multiplicity automata. JACM 47(3) (2000) 506–530
5. Bergadano, F., Varricchio, S.: Learning behaviors of automata from multiplicity and equivalence queries. SIAM J. Comput. 25(6) (1996) 1268–1280
6. Berstel, J., Reutenauer, C.: Rational Series and Their Languages. Volume 12 of EATCS Monographs. Springer (1988)
7. Boggs, P.T., Tolle, J.W.: Sequential quadratic programming. Acta Numerica 4 (1995) 1–51
8. Carlyle, J., Paz, A.: Realizations by stochastic finite automata. Journal of Com- puter and System Sciences 5(1) (1971) 26–40
9. Chen, Y.F., Hsieh, C., Lengál, O., Lii, T.J., Tsai, M.H., Wang, B.Y., Wang, F.: PAC learning-based verification and model synthesis. In: ICSE. (2016) 714–724
10. Fliess, M.: Matrices de Hankel. J. Math. Pures Appl 53(9) (1974) 197–222
11. Goldreich, O., Goldwasser, S., Ron, D.: Property testing and its connection to learning and approximation. JACM 45(4) (1998) 653–750
12. Herd, B., Miles, S., McBurney, P., Luck, M.: Quantitative analysis of multiagent systems through statistical model checking. In: Engineering Multi-Agent Systems. (2015) 109–130
13. Kwiatkowska, M.: Quantitative verification: Models, techniques and tools. In: ESEC/FSE, ACM (2007) 449–458
14. Legay, A., Delahaye, B., Bensalem, S.: Statistical model checking: An overview. In: RV. (2010) 122–135
15. Nesterov, Y.: Squared functional systems and optimization problems. In: High Performance Optimization. (2000) 405–440
16. Ohnishi, H., Seki, H., Kasami, T.: A polynomial time learning algorithm for rec- ognizable series. IEICE Transactions on Information and Systems 77(10) (1994) 1077–1085
17. Sen, K., Viswanathan, M., Agha, G.: Statistical model checking of black-box prob- abilistic systems. In: CAV. (2004) 202–215
18. Silberschatz, A., Galvin, P.B., Gagne, G.: Operating System Concepts. 8th edn. Wiley Publishing (2008)
19. Valiant, L.G.: A theory of the learnable. CACM 27(11) (1984) 1134–1142
20. Walkinshaw, N.: Assessing test adequacy for black-box systems without specifica- tions. In: ICTSS. (2011) 209–224
21. Zuliani, P., Platzer, A., Clarke, E.M.: Bayesian statistical model checking with application to Stateflow/Simulink verification. FMSD 43(2) (2013) 338–367