Tez No	İndirme	Tez Künye	Durumu
434272		Race detection techniques for applications using asynchronous programming models / Asenkron programlama modellerini kullanan uygulamalar için yarış durumu yakalama teknikleri Yazar:ERDAL MUTLU Danışman: DOÇ. DR. SERDAR TAŞIRAN Yer Bilgisi: Koç Üniversitesi / Fen Bilimleri Enstitüsü / Bilgisayar Bilimleri ve Mühendisliği Ana Bilim Dalı Konu:Bilgisayar Mühendisliği Bilimleri-Bilgisayar ve Kontrol = Computer Engineering and Computer Science and Control ; Bilim ve Teknoloji = Science and Technology Dizin:	Onaylandı Doktora İngilizce 2016 149 s.
Asenkron programlama modelleri, mobil, masaüstü ve web uygulamaları gibi modern bilişim platformlarındaki eşzamanlı geliştirme uygulamalarında yaygın kullanımdadır. Bütün eşzamanlı programlarda olduğu gibi, asenkron programlarda da akış mantığını oturtmak geliştirici için zorlayıcıdır. Geçmişten günümüze gelmiş eşzamanlı yapılardan (örn. iş parçacıkları) farklı olarak, asenkron yapılarda (örn. geri çağırma) yürütmenin doğrusal bir sıralaması olmadığından ve bu sıralama asenkron olayların icrasına bağlı değişebildiğinden, bu yapılar kontrol ve veri akışını tersine çevirebilir. Bu durumda yakalaması güç eşzaman hataları ortaya çıkabilir ve bu hatalar farkedilmesi, yeniden üretilmesi ve tamir edilmesi zor olduğundan yazılım sürecinde ciddi etkilere sebep olabilir. Yarış durumları, eşzamanlı programlarda istemsiz belirsizliğin ana kaynağı olarak görülmekte ve yüksek seviyelerdeki eşzaman hatalarının göstergesi olarak görülmektedir. Geçmişten günümüze gelmiş eşzamanlı programlama modellerinde yarış durumlarını ortaya çıkarmak için hem araştırma çevrelerinden hem de sanayi çevrelerinden yoğun ilgi gösterilmiş olsa da, asenkron programlama modellerinde yarış durumlarını ortaya çıkarmak için kullanılacak metodlara kritik bir ihtiyaç vardır. Bu tez, bahsedilen ihtiyaçları karşılamak için, eşzaman methodu olarak asenkron programlama yapıları kullanan uygulamalarda yarış durumlarını ortaya çıkarmak için yeni teknikler sunmaktadır. Sunduğumuz bu yarış durumu belirleme tekniği farklı asenkron programlama modelleri üzerine uygulanabilir. Ana olarak, JavaScript web uygulamaları ve veriakışı programlama yapılarını paylaşımlı hafıza üzerine uygulayan melez programlama modelleri üzerinde odaklandık. Tekniğimiz; statik ve dinamik analiz yaklaşımlarının avantajlarını biraraya getirmeyi amaçlamaktadır. Yürütme kodu sadece bir kere çalıştırılır, fakat birçok yürütme sıralaması statik analiz yaklaşımı kullanılarak incelenir. Bu tekniğin temelindeki görüş, tekniğin paylaşımlı hafıza noktaları üzerindeki eşzamanlı değişimleri farklı sıralamalarda birbirinden bağımsız incelemek yerine birleştirilmiş bir yapıda saklamasından gelir. Tekniğimizi açıklamanın bir yolu, belirli bir yürütme için olası farklı sıralamaları gözönünde bulundurarak, komşu yürütme sıralamalarını tek bir yürütme üzerinden incelemektir. Çalışmamızın ilk adımı olarak, JavaScript web uygulamalarındaki asenkron yapıları kullanıcı etkileşimi ve sunucu yanıtları üzerinden inceledik. öncelikle, yarış durumlarının web uygulamalarındaki zararlarını belirleyebilmek için rastgele seçilmiş ve sistematik seçilmiş sıralamalı sunucu istemleri (XMLHttpRequest) kullanılarak deneysel çalışmalar yapılmıştır. Diğer uygulama çeşitlerine nazaran, web uygulamaları geçici durumlarda gözlenen yarış durumları konusunda, etkilerin kısa ömürlü olmasından dolayı daha affedici bir yapıya sahiptir. Bunun sebebi, bu yarış durumlarının sadece programın gözle görülmeyen kullanıcı kısımlarında oluşması ya da, en kötü ihtimalle, kullanıcı arayüzünde farkedilmeyen veya sayfayı yenileyerek yok edilebilen aksaklıklardan oluşmasındandır. Bu deneysel çalışmanın sonuçlarından yola çıkarak, web uygulamarındaki yarış durumlarında, kalıcı durum üzerinde odaklanmanın daha kullanışlı olacağını önerdik. Bu kalıcı durumlar kullanıcı tarafında saklanan çerezler, localStorage ve sessionStorage mekanizmaları olabileceği gibi sunucu tarafındaki yan etkiler de olabilir. Geliştirdiğimiz tekniği, asenkron yapıları yoğun şekilde kullanan 26 web sitesi üzerinde değerlendirdik ve zararsız yarışların (geçici durumlarda gözlenen) zararlı yarışlardan (kalıcı durumlarda gözlenen) çok daha yaygın olduğunu gözlemledik. Son olarak, JavaScript kütüphanelerinde yarış durumu ile ilgili hataları bildirmek için kullanılan yeni bir asenkron yapı -Promiseler- üzerinde bir araştırma çalışması hazırladık. Tezin ikinci kısmında, veriakışı yapılarını paylaşımlı hafıza programlama modelleriyle biraraya getiren melez programlama modelleri üzerinde çalıştık. Bu melez programlama modelleri, programcılara görevleri ana yürütme birimi olarak ve aralarındaki veri bağıntılarıyla birlikte tanımlamak için veriakışı soyutlaması sağlar. Saf veriakışı modelinin tersine, ki bu model görevlerin yan etki olmadan yürütüleceğini varsayar, melez modeller görevlerin iş parçacığı senkronizasyonu kullanarak (örn. kilit ve işlem belleği) veri paylaşmasına olanak verir. Olası yürütme sıralamaları ve uygulamayı oluşturan görevleri araştırmak için, olasılık garantili rastgeleleştirilmiş bir araştırma tekniği geliştirdik. Daha sonra, melez programlama modellerinde yarış durumlarını ortaya çıkarmak için kullanılacak modüler bir yarış belirleme tekniği geliştirdik. Farklı programlama modelleri tarafından -örneğin veri akışı ve paylaşımlı hafıza- dayatılan önce-olur ilişkileri (yürütme sırası) için modüler bir gösterim sunduk. Bu programlama modellerine örnek olarak veriakışı ve paylaşımlı hafıza verilebilir, ki bunlar belırleme mekanizmasını kilit bazlı ya da işlem hafızası bazlı senkronizasyon sistemleri gibi farklı tipteki paylaşımlı hafızalar için genişletmede kullanılabilir. Son olarak, geliştirdiğimiz yarış belirleme mekanizmasını genel bir prototip araç olarak kodladık, böylece geliştirdiğimiz bu araç farklı tiplerdeki melez programlama modelleri için de kolayca genişletilebilir.
Asynchronous programming models has become ubiquitous in concurrent application development for the modern computation platforms, i.e. mobile, web and desktop applications. Similar to all concurrent programs, reasoning about asynchronous programs is challenging for the developers. Different than legacy concurrency constructs (i.e. threads), asynchronous constructs (i.e. callbacks) can invert the control and data flow as the execution order is not linear and may change depending on the dispatch of asynchronous events. This may result in subtle concurrency bugs that can have a big impact on the development cycle as it is notoriously hard to detect, reproduce, and fix them. Data races have been considered as the main source of unintended non-determinism in concurrent programs and seen as a symptom of a higher-level concurrency error. Although race detection in legacy concurrent programming models have attracted a great deal of attention from both the research communities and commercial counterparts, there is a critical need for race detection techniques for asynchronous programs. To address these needs, this thesis introduces techniques for detecting data races on applications using asynchronous programming constructs as a way of concurrency. We introduce race detection technique that is applicable to different asynchronous programming models. We focused mainly on JavaScript web applications and applications using hybrid programming models that integrates dataflow programming construct into shared memory programming models. Our techniques attempts to combine advantages of both static and dynamic analysis. We executed the application code only once, yet we explore multiple execution order with the help of our static analysis approach. The key idea behind our analysis technique is that it encodes the effects of concurrent updates on the shared state by merging the values as opposed to separately considering different orderings. One way to see our approach is that we explore neighboring schedules for a particular runtime execution by analyzing possible re-orderings of the concurrent entities with a single pass over the observed execution. As the first part of our study, we explored JavaScript web applications using asynchronous constructs for user interaction and server requests. First, we conducted empirical studies for identifying the real damages of data races in the web applications by devising randomized and systematic exploration of server requests (XMLHttpRequests) orderings. As opposed to other types of applications, web applications have a more forgiving nature for data races on transient state, since their effects are ephemeral. This is because these races only occur in invisible to the user portions of the program state, or, at worst, UI glitches that are either unnoticed by the user, or disappear if the user reloads the page. In the light of our empirical study, we suggested that a more useful way to think about data races on the web is by focusing on persistent state, such as client-local cookies, localStorage and sessionStorage mechanisms, as well as server-based side effects. We evaluated our technique on 26 web sites that heavily uses asynchronous constructs, we demonstrate that benign races (on transient state) are considerably more common than harmful ones (on persistent state). Finally, we conducted an exploratory study on the reported race related bugs on JavaScript libraries that uses new asynchronous constructs: Promises. In the second part of the thesis, we worked on hybrid programming models combining dataflow constructs with share memory programming model. These hybrid programming models provide programmers with dataflow abstractions for defining tasks as the main execution unit with corresponding data dependencies between each other. Contrary to the pure dataflow model which assumes side-effect free execution of the tasks, these models allow tasks to share the data using some form of thread synchronization, such as locks or transactional memory (TM). We devised a randomized exploration technique with probabilistic guarantees for exploring possible execution orders of the tasks composing the application. Later, we devised a modular race detection technique which can be used for detecting data races in hybrid programming models. We presented a modular representation of happens before relations (execution orders) imposed by different programming models, i.e. dataflow and shared memory, which can be used for extending the detection mechanism for different type of shared memory synchronization systems, i.e. lock-based, transactional memory. Finally, we implemented our detection mechanism as a generic tool prototype that can be easily extended for different type of hybrid programming models.