Software Assurance by Bounded Exhaustive Testing

Title
Software Assurance by Bounded Exhaustive Testing
Authors
David Coppit, Jinlin Yang, SarfrazKhurshid, and Kevin Sulliva
Abstract
Bounded Exhaustive Testing (BET) adalahteknikverifikasimasukanperangkatlunak.Penelitiansebelumnyamengatakanbahwa BET hanyabisamengungkapkanfaults di sistemkecildenganmasukan yang tidakbegitukompleks. Namunkinihasilpenelitianterbarumengatakanbahwa BET, dikombinasikandenganabstraksiterhadapspesifikasidanteknikpemfaktoran, bisamenjaditoolsverifikasiperangkatlunak yang bisadiandalkan.
Introduction
Penelitiansebelumnyamenunjukkanbahwa BET mampudigunakanuntukmengetesmodulperangkatlunakdenganstruktur data sederhana.
Yang menjadipertanyaan-nyamampukah BET diterapkanpadamodulperangkatlunakbesar. Denganmengacupadahipotesa Jackson, bahwapengetesanmasukankecilbisamengungkapkanfault, makakalauditerapkanpadapengetesanmasukanbesarakanmampumengungkapkanfaultdalamporsi yang lebihbesar
Untukitu, pengetesandilakukandengansubjek Galileo tools untuk memodelkan danmenganalisis reliability (denganpemodelan DFT, Dynamic Fault Trees[5], [6], [7]), fault-tolerant, sistemterkomputerisasi.
Percobaandilakukandenganmengabstraksispesifikasimasukan yang di-offload-kanke Alloy [8], agar Alloy tidakkehabisanmemoribilaberjalansecaraonload.
Lalu detail abtraksidicatat, denganmenggunakanTestEra[9]untukmembangkitkanmasukanabstrak. kemudian, mengkombinasikanmasukanabstrakdengan detail-detailnyauntukmenyusunmasukanspace-nya.
Dengantekniktersebut, mampumengungkapkanfault-fault yang ada.Percobaanditerapkanpadalebihdari 250.000 masukan DFT.
Methods and Materials
*DFT*
DFT adalahgrafikpemodelansistem, terdiridaribasic node (representasieventdalamsistem), gates node (representasifailure event yang munculsebagaifungsidarieventlainnya, bisastatik[And Gates] ataudinamik [Priority-And Gates]), danconstraint (representasibatasandarievent, bisa FDEP [kegagalan yang terjadisecaracascade] atau SEQ [kegagalansesuaiurutan]).

Spare gatesterjadijikadanhanyajikasemuamasukannyagagalataumenjaditidakada. Sistembekerjabilaevent1 memberimasukan.Bilaevent1 gagalataumenjaditidakada, makaspare gateakanmendapatmasukandarievent2. FDEP mengindikasikanbahwabilaterjadikegagalanpadaevent1 makaevent3 jugaikutgagal.Akibatnya, sistemakanberhenti total, bilaevent1 danevent2 mengalamikegagalan.
*Galileo*
Adalahtoolsuntukmenganalisa DFT. Galileo akanmenguraikanpohon DFT kedalam sub-sub pohonuntukdipecahkansecaraterpisahdenganmenggunakan DFT solvers (dynamic solver yang menterjemahkan Markov chains [10]ataustatic solver yang menterjemahkanmenjadi BDD [5]), nantinyahasilakandirangkaikembaliuntukmemperolehhasilakhir.
Penelitian BET inibertujuanuntukmengevaluasiapakahmungkinuntukmenggunakan BET untukmengetes Galileo.
PengetesandilakukandenganmembangkitkanmasukandenganmenggunakanTestEra (framework testing class-classpada Java).Lalu output-nyadicekmenggunakan Nova solver (Galileo dynamic analyzer) sebagaioracle-nya.
Pengetesandilakukandenganlingkupkecilterlebihdahulu.Penelitiantahapiniberhentisaatlingkuptujuantelahdipenuhiatausaatpengetesanperangkatlunakmenjaditidakmungkinakibatkegagalansistem.
Results
Dari hasilpengetesan, kecepatanoraclemenurunseiringdenganmeningkatnyamasukanfaulttree.Sedikitsulituntukmengetesdengan 6 masukantanpamengoptimalkankinerjaoracle.

Jumlahmasukan yang dibangkitkan, hingga 8 cakupanevent.Pengetesanmampumeng-instansiasisemua DFT konkrithingga 6 event.
Selainitu, BET mampumengungkapkan 8 faultspadagalileo, 3 faultspadaspesifikasidan 3 faultspadaoracle.
Discussion and Recommendations
Ada keterbatasandalampenelitianini, yaitu:
-          TestErakurangmampumenanganitipe data numericdenganbaik.
-          Alloy tidakmendukung data integer.
-          Bilaadafault di oracleatau di spesifikasi, maka BET tidakdapatditerapkan.
-          Hasil statistic reliabilitassistemtidakdapatdidasarkanpadapenggunaan BET.
Akan tetapi, denganketerbatasantersebut, BET merupakantoolsverifikasi yang mampumengungkapfault, baik yang sifatnyasubstansialmaupunfault yang halus, padasuatusistemdenganukurantertentu.
References
[1]     D. Jackson and C.A. Damon, “Elements of Style: Analyzing a Perangkatlunak Design Feature with a Counterexample Detector,” IEEE Trans. Software Eng., vol. 22, no. 7, pp. 484-495, July 1996.
[2]     D. Coppit and K.J. Sullivan, “Galileo: A Tool Built from Mass-Market Applications,” Proc. Int’l Conf. Software Eng., pp. 750-753, June 2000.
[3]     J.B. Dugan, K.J. Sullivan, and D. Coppit, “Developing a Low-Cost High-Quality Software Tool for Dynamic FaultTree Analysis,” IEEE Trans. Relativity, vol. 49, no. 1, pp. 49-59, Mar. 2000.
[4]     K.J. Sullivan, J.B. Dugan, and D. Coppit, “The Galileo FaultTree Analysis Tool,” Proc. Int’l Fault-Tolerant Computing Symp., pp. 232-235, June 1999.
[5]     S.A. Doyle and J.B. Dugan, “Dependability Assessment Using Binary Decision Diagrams (BDDs),” Proc. Int’l Fault-Tolerant Computing Symp., pp. 249-258, July 1995.
[6]     J.B. Dugan, S. Bavuso, and M. Boyd, “Dynamic Fault-Tree Models for Fault-Tolerant Computer Systems,” IEEE Trans. Relativity, vol. 41, no. 3, pp. 363-377, Sept. 1992.
[7]     W.E. Vesely, F.F. Goldberg, N.H. Roberts, and D.F. Haasl, “FaultTree Handbook,” Technical Report NUREG-0492, US Nuclear Regulatory Commission, Washington, D.C., 1981.
[8]     D. Jackson, “Micromodels of Software: Modelling and Analysis with Alloy,” http://sdg.lcs.mit.edu/alloy/reference-manual.pdf, 2001.
[9]     D. Marinov, A. Andoni, D. Daniliuc, S. Khurshid, and M. Rinard, “An Evaluation of Exhaustive Testing for Data Structures,” Technical Report MIT-LCS-TR-921, MIT CSAIL, Cambridge, Mass., Sept. 2003.
[10]   M.A. Boyd, “Dynamic FaultTree Models: Techniques for Analysis of Advanced Fault Tolerant Computer Systems,” PhD dissertation, Dept. of Computer Science, Duke Univ., Durham, N.C., Apr. 1991.

Precise Interface Identification to Improve Testing and Analysis of Web Application

Title
Precise Interface Identification to Improve Testing and Analysis of Web Application
Authors
William G.J. Halfond, SaswatAnand, and Alessandro Orso.
Abstract
Ada banyakpendekatanuntukmengidentifikasiantarmuka (Application Programming Interface) sebuahwebaplikasi.Akan tetapi, beberapapendekatan yang ada, memilikibanyakkekurangan, sehinggabisamembatasiefektifitasjaminankualitaswebtersebut, khususnyauntukaplikasiweb yang kompleks.
Makalahinimengenalkanpendekatanbaruuntukmengidentifikasiantarmukaberdasarkanpada proses eksekusisimbolik.
Introduction
Beberapapendekatanidentifikasiterhadapantarmuka yang berkembangadabermacam-macam. Ada pendekatan yang mengandalkanspesifikasiantarmuka yang dikembangkanolehpihakdeveloper[1,2,3]. Meskipunspesifikasi yang dikembangkanolehpihakdeveloperbisadenganakuratmengindikasikansifatdariaplikasi, namun, biasanya, proses tersebutmembutuhkanbanyakwaktu. Pendekatanlainnya, [4, 5] berinteraksidenganaplikasiwebpadasaatruntimedanmenggunakananalisadinamisuntukmengidentifikasiantarmuka yang munculsaatberinteraksi. Akan tetapi, kelemahandaripendekataniniadalahtidakadanyajaminanakankelengkapanantarmuka-nyadanmungkinuntuktidakdapatmengidentifikasiantarmuka yang tersembunyi (hidden). Bentukpendekatanlainnyaadalahdenganmetodeanalisastatis[6], yang kelemahannyaterdapatpadaketidaktepatannyadalam proses identifikasi, sehinggabisamenghasilkansuatuanalisa yang sifatnyafalse positivemaupunfalse negative.
Pendekatanbaru yang ditawarkanolehmakalahiniyaitupenggunaaneksekusisimbolikuntukmengidentifikasiantarmuka.
Methods and Materials
Dalameksekusisimbolik, sebuah program dieksekusidalamkeadaan normal sepertibiasa, hanyasaja program tersebutmenjalankansuatumasukansimbolik yang mewakilisuatunilaitertentu[7].
Untuklebihjelasnyamengenaieksekusisimbolik, dijelaskanmelaluicontohberikut :

Padapotongan program di atas, input a dan b akanmewakilisuatunilaisimbolik. Baris 1, 2 dan 4 di dalamnyamengandungalur program kondisional (PC, path condition). Jadi, eksekusisimbolikuntukmethod fooakanmenghasilkan PC sebanyak 6 pathataujalur, daribaris 1 hingga 6, berupa :

Pendekataneksekusisimboliksendiriterdiridaritigalangkah, yaitu :

• Symbolic Transformation

Ada duatransformasi, yang pertamayaituuntukmengidentifikasinilai-nilaisimbolik, dimananilai-nilaitersebutharusdiperkenalkandengantepatkedalam model aplikasi IP.Yang keduaadalahuntukmenggantikan operator domain dengan symbol khusus yang tepat, untukmemperbaharuikondisijalur (PC) saataplikasitersebutdieksekusisecarasimbolis.

• Generating Path Conditions

Ada empatlangkah, yaitupengaksesan IP, pengkonversiankedalamtipenumerik, pembandinganstring, danpembatasanaritmatik.

• Interface Identification

Padalangkahini, antarmukaakanditerimasetelah PC dianalisadanstatesimbolikdibangkitkanolehlangkahkedua.

Results

Dari hasilevaluasimenunjukkanbahwaefisiensiteknik yang diterapkanpadametodeinisebandingdengantekniklain, mampumeraihtingkatpresisi yang lebihtinggidanmeningkatkankinerjateknikpenjaminankualitasterhadapinformasiantarmuka. Secarakhusus, denganmenggunakanpendekataniniakanmengarahpadaserangkaianpengetesan yang lebihsedikitnamundengancakupan data yang lebihtinggi.

References

[1] A. A. Andrews, J. O_utt, and R. T. Alexander.Testing Web Applications by Modeling with FSMs. In Software Systems and Modeling, pages 326-345, July 2005.

[2] X. Jia and H. Liu.Rigorous and Automatic Testing of Web Applications.In 6th IASTED International Conference on Software Engineering and Applications, pages 280{285, November 2002.

[3] F. Ricca and P. Tonella.Analysis and Testing of Web Applications. In International Conference on Software Engineering, pages 25-34, May 2001.

[4] S. Elbaum, K.-R.Chilakamarri, M. F. II, and G. Rothermel.Web Application Characterization Through Directed Requests. In International Workshop on Dynamic Analysis, pages 49-56, May 2006.

[5] Y. Huang, S. Huang, T. Lin, and C. Tsai.Web Application Security Assessment by Fault Injection and Behavior Monitoring. In Proc. of the 12^th International World Wide Web Conference (WWW 03), pages 148-159, May 2003.

[6] Y. Deng, P. Frankl, and J. Wang.Testing Web Database Applications. SIGSOFT Software Engineering Notes, 29(5):1-10, 2004.

[7] J. C. King. Symbolic Execution and Program Testing.Commun. ACM, 19(7):385-394, 1976.

Evaluating Test Suites and Adequacy Criteria Using Simulation-Based Models of Distributed Systems

Title
Evaluating Test Suites and Adequacy Criteria Using Simulation-Based Models of Distributed Systems
Authors
Matthew J. Rutherford, Antonio Carzaniga and Alexander L. Wolf.
Abstract
Teskriteriakecukupanmerupakansuatu tools ataualatuntukmengorganisasikanserangkaianaktifitaspengetesanterhadapsistem. Teskriteriakecukupantersebuttelahbanyakdibahas, di antaranyaadateskriteriakecukupandalamkontekssekuensial[1]dandalamkontekssistemkonkuren[2].Namun, belumadateskriteriakecukupan yang secaraspesifikdibahasdalamlingkupsistemterdistribusi.Makalahinimembahasmengenaihaltersebut.
Introduction
Makalahinimembahasmengenaiframeworkteskriteriakecukupan, bukanpadapenciptaankriteriabaru.Jadi, diharapkanmampumembantuengineer, denganmemberikanprediksimengenaitingkatefektifitaskandidatpengetesandankriteriakecukupan yang cocokuntuksistemtersebuttanpaharusmengeksekusikeseluruhanperangkatpengetesankedalamsistem.Sebab, tingkatefektifitassuatuteskriteriakecukupanbergantungpadasistem yang menjadiobjekpengetesannya.Makalahinijugamembahasmengenaibagaimanamenentukanteskecukupan yang paling efektifuntuksistem yang sedangdiuji.
Metode yang diterapkandalamteskriteriakecukupaninimendefinisikankriteriakecukupandalam model berbasissimulasidenganpenerapanteknikdiscrete-event.Discrete-event simulationmengorganisasikan proses-proses danevent yang terjadidalamsistem yang bersangkutan.Proses-proses tersebutmewakilientitasdinamisdalamsistemterdistribusi yang disimulasikan, sedangkaneventdigunakanoleh proses-proses tersebutuntuksalingbertukarinformasi.
Simulasisendirimerupakanabstraksidarispesifikasisistemterdistribusi yang bisa di-eksekusi, dimanabahasaspesifikasitersebutadalahmerupakanbahasapemrogramandalamsistemterdistribusi.
Selainitubisajugamenggunakanmetodeberbasissimulasidenganmetodefault-based analysis.Kombinasiduametodeinibisajugaditerapkansekaligusuntukmembantumengidentifikasirangkaian proses sepertiapa yang paling cocokuntukditerapkanpadasuatusistem.
Methods and Materials
Untukdapatmenentukanteskriteriakecukupan yang efektif, setidaknyadiperlukanmetodeberbasissimulasi, denganalurpengetesansebagaiberikut :

Langkah 1 mengharuskanengineeruntukmemilihkriteriakecukupan yang cocokuntukmengorganisasikankeseluruhan proses. Langkahke 2 hingga 4 diulanghinggaengineermampumemutuskanperangkatpengetesanmana yang paling cocokuntuksistemtersebut. Langkah 5 merupakan proses pemetaan input vector untukdiimplementasikedalam domain sistemtersebut, kemudiandilakukan proses eksekusitiap-tiapkasuspengujiandalamimplementasitersebut (langkah 6). Kegiatanpengetesanselesai, danhasilnyabisadipantaumelaluihasildaripengetesan yang dihasilkanolehsistemtersebut (langkah 8).

Metodelainnya, ataumetodefault-based analysis, mencobauntukmembandingkankriteriakecukupandengankemampuannyauntukmendeteksiklas-klas yang didalamnyamengandungfault (kesalahan).

Pendekatandenganmenerapkanfault-based analysismaupunsimulation-basedmaupunkombinasidarikeduanya, diterapkandalamtigaskenario yang berbeda, yaitu :

• Conventional

Cara konvensionaluntukmenggunakanpengetesanberbasissimulasiadalahdenganmemilihtujuanumumdarikriteriakecukupan yang akandigunakan, kemudianmemilihperangkatpengetesanmana yang paling cocokdengankriteria yang telahditentukansebelumnya.

• Boosting

Padaskenarioini, engineermemilihlebihdarisatukriteriakecukupankemudianmenerapkanseperangkatpengetesan yang sesuaidengankriteria yang telahdipilihsebelumnya.Dalamskenarioini, engineermenerapkanmetodefault-based analysis.Penggunaanskenarioinilebihbanyakmemakanbiayadaripadaskenariokonvensional, sebabpilihankriteriakecukupan yang digunakanlebihdarisatudanperangkatpengetesan yang diterapkanharusmelaluianalisaberbasiskesalahan (fault-based analysis) terlebihdahulu.
Akan tetapi, denganskenarioini, resikointracriterionlebihkecildibandingkandenganskenariokonvensional.

• Ranking

Dalamskenarioini, engineersecararasionalmemilihsatudaribeberapakriteria yang ada yang sekiranya paling efektifbiladiterapkandalamsistem yang akandiuji. Jadi, dalamskenarioini, engineersekaligusmenerapkanskenarioboosting, kemudianberdasarkanperingkat (ranking) efektifitasterbaik, kriteriakecukupandanperangkatpengetesannyadipilih.

Dengandemikian, metodeberbasissimulasibisaditerapkansecaralangsunguntukmengevaluasiperangkatpengetesan yang paling cocokberdasarkankriteria, disesuaikandenganlingkungansistemdankodesimulasi yang digunakan.

Sedangkanmetodefault-based analysisjauhlebihmahaldikarenakanmetodeinimemerlukanbeberapaeksekusisecarasimultanuntuksetiaptest casedalamsuaturangkaianperangkatpengetesan.

Results

Dari hasilpenelitiandiketahuibahwa :

• Discrete-event simulationmerupakancara yang efektifuntukmengetessuatuimplementasi
• Fault-based analysisbisadigunakanuntukmemprediksitingkatefektifitasdarirangkaianperangkatpengetesan yang paling cocokuntuksuatusistemterdistribusi
• Teknikfault-basedbisadigunakanuntukmemprediksitingkatefektifitasdarisuatukriteriakecukupan.

References

[1]   P. Frankl and E. Weyuker, “An Applicable Family of Data Flow Testing Criteria,” IEEE Trans. Software Eng., vol. 14, no. 10, pp. 1483-1498, Oct. 1988.

[2]   R.H. Carver and K.-C. Tai, “Use of Sequencing Constraints for Specification-Based Testing of Concurrent Programs,” IEEE Trans. Software Eng., vol. 24, no. 6, pp. 471-490, June 1998.

Efficient Online Schedulability Tests for Real-Time Systems

Title
Efficient Online Schedulability Tests for Real-Time Systems
Authors
Tei-Wei Kuo, Li-Pin Chang, Yu-Hua Liu and Kwei-Jay Lin.
Abstract
Penjadwalanpengetesansistemtelahbanyakdiusulkansebelumnya.Akan tetapi, penjadwalanpengetesansistemtersebuttidakjarangmengalamikegagalan, terutamabilasistemsedangmenanganibeban yang berat.Makalahinimembahasmengenaipenjadwalanpengetesanuntuksistemonline yang lebihefisien.
Introduction
Dewasainiserverkomputerdengankemampuan real-time banyakdibutuhkangunaberbagaimacamkebutuhan, untukmendukungberbagaikeperluanseperti video conference, distant learning, hiburanonline, permainanonline, dan lain-lain.
Olehsebabitu, dibutuhkansuatupengetesanserver yang terjadwal agar serverkomputertersebutdapatberjalandenganmaksimal.
Telahbanyakdikembangkan model pengetesanserverdengansistempenjadwalan yang memilikikemampuan yang tidakdiragukan[1][2][3], akantetapiketepatanpengetesantersebutharusdibayardenganbanyaknyawaktu yang diperlukanuntukmengetessistem. Hal inikurangcocokterutamauntuksistemonlinedimanawaktuadalahunsurpenting yang tidakbisadiacuhkan.
Methods and Materials
Alokasisumberdayasecaraonlinesebelumnyapernahdibahasoleh Liu and Layland[4]denganmengenalkankonsepfaktorutilisasi (U), yaitudenganmengadakansuatupengetesancepat (quick test) untukmenentukanpenjadwalan proses periodikdenganwaktueksekusidanperiodetertentu.
Faktorutilisasitersebutdidefinisikansebagaiberikut :

Dimana c_i = kebutuhankomputasi
p_i = periode proses Ti
Penjadwalansejumlah n proses dijaminbilafaktorutilisasidari proses tersebuttidaklebihdari U, dimanaU(n) = n (2^1/n – 1) darialgoritma [4].
Akan tetapi, algoritma [4] gagaluntukmenangani proses yang banyak di-load di sistem.
Selainalgoritma [4] masihbanyakalgoritmalaindenganteknik-teknik yang berbeda yang diterapkandalampenjadwalanpengetesansistem. Namun, penjadwalantersebutdinilaikurangtepatkhususnyabilasistemsedangmengalamioverloaded.
Berikutadalahalgoritma yang diterapkandalamsistemini, khususnyauntuksistemuniprosesor :

Berikutadalahalgoritma yang diterapkanuntukpengetesansistemonlinedenganuniprosesor :

Langkah 1 dan 2 menurunkanjumlah root yang berkorespondensidanakumulasidariutilisasi CPU untuk proses-proses denganperiodetidaklebihdari p. Kemudian loop antaralangkah 5 dan 11 menurunkanjumlah root yang berkorespondensidanakumulasidariutilisasi CPU untuk proses-proses denganperiodetidaklebihdari p_i.
Sedangkanalgoritmauntukpenjadwalanpengetesansistemonlinedenganmultiframe :

Algoritmainihampirsamadenganalgoritmasebelumnya, yang berbedahanyapadaperlunya proses menjaganilai RSR-nya.
Results
Dari hasilpenelitiandiperolehhasilbahwauntuksistemuniprosesordiketahuibahwaadanyarasiojaminanmengenaipenjadwalanpengetesan yang lebihbaikdaripadaalgoritma-algoritma yang pernahdikemukakansebelumnya, terutamamenyangkutmasalahjumlahfrekuensikemunculan proses saatsistemsedangmengalamioverload.
Hasil yang samajugaditunjukkanpadaalgoritmapenjadwalanuntuksistemdenganmultiframe. Banyak proses yang berhasildiidentifikasiuntukdijadwalkanpengetesannyaberdasarpadaalgoritmapenjadwalan RMS.
Kesimpulanperbandinganpenjadwalantesdapatdilihatpadatabel di bawahini :

References
[1]   A.K. Mok and D. Chen, “A Multiframe Model for Real-Time Tasks,” IEEE Trans. Software Eng., 1997.
[2]   A. Burchard, J. Liebeherr, Y. Oh, and S.H. Son, “New Strategies for Assigning Real-Time Tasks to Multiprocessor Systems,” IEEE Trans. Computers, 1995.
[3]   C.C. Han and H.Y. Tyan, “A Better Polynomial-Time Schedulability Test for Real-Time Fixed Priority Scheduling Algorithms,” Proc. IEEE 18th Real-Time Systems Symp., 1997.
[4]   C.L. Liu and J.W. Layland, “Scheduling Algorithms for Multiprogramming in a Hard Real-Time Environment,” J. ACM, vol. 20, no. 1, 1973.