Computer Science Technical Reports

Permanent URI for this collectionhttps://hdl.handle.net/20.500.12588/2094

Browse

Now showing 1 - 20 of 107

Monitoring Dense-Time, Continuous-Semantics, Metric Temporal Logic
(UTSA Department of Computer Science, 2012-12) Baldor, Kevin; Niu, Jianwei
The continuous semantics and dense time model most closely model the intuitive meaning of properties specified in metric temporal logic (mtl). To date, monitoring algorithms for mtl with dense time and continuous semantics lacked the simplicity the standard algorithms for discrete time and pointwise semantics. In this paper, we present a novel, transition-based, representation of dense-time boolean signals that lends itself to the construction of efficient monitors for safety properties defined in metric temporal logic with continuous semantics. Using this representation, we present a simple lookup-table-based algorithm for monitoring formulas consisting of arbitrarily nested mtl operators. We examine computational and space complexity of this monitoring algorithm for the past-only, restricted-future, and unrestricted-future temporal operators.
Reducing Field Table Size in the Icon Translator
(UTSA Department of Computer Science, 1995-12-16) Hatch, Richard; Jeffery, Clinton L.
The size of generated code includes many pieces of static information about a program in addition to its actual instructions. In the case of the Icon programming language, a table used in the implementation of the record data type may become quite large. This report describes an implementation of compression techniques that saves 3-12 kilobytes per binary for typical graphical applications, and much more space (over 400 kbytes in one case) for larger programs using many records.
An Empirical Study of Continuous Integration Failures in TravisTorrent
(UTSA Department of Computer Science, 2018-07-03) Hassan, Foyzul; Wang, Xiaoyin
Continuous Integration (CI) is a widely used development practice where developers integrate their work after submitting code changes at central repository. CI servers usually monitor central repository for code change submission and automatically build software with changed code, perform unit testing, integration testing and provide test summary report. If build or test fails developers fix those issues and submit the code changes. Continuous submission of code modification by developers and build latency time creates stalls at CI server build pipeline and hence developers have to wait long time to get build outcome. In this paper, we categorize CI failures from TravisTorrent data set and studied the frequency of different failures. Our study on 1,187 CI failures from TravisTorrent data set shows that 829 of the CI failures are test failures, compared with 252 build script errors, 49 JavaDoc errors, and 67 stylechecking errors. It also reveals that 10.8% of CI-failure repair commits contains only build script revisions, and 25.6% CI-failure repair commits involve at least one build script revision.Furthermore, we proposed build prediction model that uses TravisTorrent data set with build error log clustering and AST level code change modification data to predict whether a build will be successful or not without attempting actual build so that developer can get early build outcome result. With the proposed model we can predict build outcome with an average F-Measure over 87% on all three build systems (Ant, Maven, Gradle) under the cross-project prediction scenario.
Virtual Machine Provisioning for Applications with Multiple Deadlines in Resource-Constrained Clouds (Extended Version)
(UTSA Department of Computer Science, 2017-07) Begam, Rehana; Wang, Wei; Zhu, Dakai
Recently, several studies have considered applications with a single time constraint (i.e., deadline) running on cloud systems. In this work, to effectively support user requests with flexible timing constraints (e.g., users may prefer expedited services and are willing to pay extra for getting their job processed at earlier times), we consider applications with multiple deadlines for being processed in resource-constrained cloud systems and investigate corresponding virtual machine (VM) provisioning schemes. Specifically, by considering the multiple deadline-bid pairs of user requests, we propose a Slope-based Time-Sensitive Resource Factor with Dominant Resource being considered to prioritize such requests. In addition, we study the mapping schemes that allocate the multiple VMs of a user request to only one or multiple computing nodes, which are denoted as Bundled vs. Distributed mappings, respectively. The evaluation results show that, compared to the single deadline schemes, the proposed VM provisioning schemes with multiple deadlines and distributed mapping can significantly improve the overall resource utilization and system benefit.
PoliDroid-AS: A Privacy Policy Alignment Plugin for Android Studio
(UTSA Department of Computer Science, 2017-05) Slavin, Rocky; Wang, Xiaoyin; Hosseini, Mitra Bokaei; Niu, Jianwei; Bhatia, Jaspreet; Breaux, Travis D.
Mobile applications frequently access personal information to meet user or business requirements. Developers are, in turn, often required to align their code with a privacy policy or to create the privacy requirements to specify the collection and use of personal information. However, it is challenging for a regular programmer to create code complying with a privacy policy. To aid app developers in such tasks, we have created PoliDroid-AS, an Android Studio plugin for the detection of code-policy misalignments and the generation of privacy specifications.
Augmented Stabilized Formulations with Fictitious Boundary Methods
(UTSA Department of Computer Science, 2016-12-12) Ranjan, R.; Feng, Y.; Chronopoulos, A.
Augmentation of the SUPS formulation was introduced earlier and successfully applied to solving incompressible Navier- Stokes equations for both two dimensional and three dimensional problems. Fictitious boundary methods (FBM) is a new methodology that aid the study of flow descriptions around solid obstacles on fixed Cartesian product grids that do not require body confirming meshes. FBM has been applied to lower order finite element and spectral/hp least squares techniques. We test the augmented stabilized finite element formulation introduced earlier, (ASUPS) to the fictitious boundary context and use it to solve incompressible flow problems. Utilizing the advantages of fictitious boundary methods we present solutions to flow around an array of two dimensional and three dimensional problems. In two dimensional flow computations we solve flow past a circular and elliptical shaped cylinders. For the ellipse shaped obstacles in a Newtonian flow field we examine the effects of varying boundary conditions and aspect ratios on the flow metrics. Finally we extend the procedures to solving two ellipse and two circular shaped obstacles facing the free stream. In three dimensional computations we examine incompressible flow around a three dimensional ellipse shaped obstacle at Reynolds number Re-200.
Stabilized and Galerkin Least Squares Formulations
(UTSA Department of Computer Science, 2016-07-17) Ranjan, R.; Feng, Y.; Chronopoulos, A. T.
We study incompressible fluid flow problems with stabilized formulations. We introduce an iterative penalty approach to satisfying the divergence free constraint in the Streamline Upwind Petrov Galerkin (SUPG) and Galerkin Least Squares (GLS) formulations, and prove the stability of the formulation. Equal order interpolations for both velocities and pressure variables are utilized for solving problems as opposed to div-stable pairs used earlier. Higher order spectral/hp approximations are utilized for solving two dimensional computational fluid dynamics (CFD) problems with the new formulations named as the augmented SUPS (ASUPS) and augmented Galerkin Least Squares (AGLS) formulations. Excellent conservation of mass properties are observed for the problem with open boundaries in confined enclosures. Inexact Newton Krylov methods are used as the non-linear solvers of choice for the problems studied. Faithful representations of all fields of interest are obtained for the problems tested.
Procedures for solving spectral/hp stabilized incompressible flow problems
(UTSA Department of Computer Science, 2016-04) Ranjan, R.; Feng, Y.; Chronopoulos, A.
In this paper we implement the element-by-element preconditioner and inexact Newton-Krylov methods (developed in the past) for solving stabilized computational fluid dynamics (CFD) problems with spectral methods. Two different approaches are implemented for speeding up the process of solving both steady and unsteady incompressible Navier-Stokes equations. The first approach concerns the application of a scalable preconditioner namely the element by element LU preconditioner, while the second concerns the application of Newton-Krylov (NK) methods for solving non-linear problems. We obtain good agreement with benchmark results on standard CFD problems for various Reynolds numbers. We solve the Kovasznay flow and flow past a cylinder at Re-100 with this approach. We also utilize the Newton-Krylov algorithm to solve (in parallel) important model problems such as flow past a circular obstacle in a Newtonian flow field, three dimensional driven cavity, flow past a three dimensional cylinder with different immersion lengths. We explore the scalability and robustness of the formulations for both approaches and obtain very good speedup. Effective implementations of these procedures demonstrate for relatively coarse macro-meshes the power of higher order methods in obtaining highly accurate results in CFD. While the procedures adopted in the paper have been explored in the past the novelty lies with applications with higher order methods which have been known to be computationally intensive.
An Elastic Mixed-Criticality Task Model and Early-Release EDF Scheduling Algorithms
(UTSA Department of Computer Science, 2016-02) Su, Hang; Zhu, Dakai; Brandt, Scott
Many algorithms have recently been studied for scheduling mixed-criticality (MC) tasks. However, most existing MC scheduling algorithms guarantee the timely executions of high-criticality (HC) tasks at the expense of discarding low-criticality (LC) tasks, which can cause serious service interruption for such tasks. In this work, aiming at providing guaranteed services for LC tasks, we study an Elastic Mixed-Criticality (E-MC) task model for dual-criticality systems. Specifically, the model allows each LC task to specify its maximum period (i.e., minimum service level) and a set of early-release points. We propose an Early-Release (ER) mechanism that enables LC tasks be released more frequently and thus improve their service levels at runtime, with both conservative and aggressive approaches to exploiting system slack being considered, which is applied to both EDF and preference-oriented earliest-deadline (POED) schedulers. We formally prove the correctness of the proposed ER-EDF scheduler on guaranteeing the timeliness of all tasks through judicious management of the early releases of LC tasks. The proposed model and schedulers are evaluated through extensive simulations. The results show that, by moderately relaxing the service requirements of LC tasks in MC task sets (i.e., by having LC tasks’ maximum periods in the E-MC model be 2 to 3 times of their desired MC periods), most transformed E-MC task sets can be successfully scheduled without sacrificing the timeliness of HC tasks. Moreover, with the proposed ER mechanism, the runtime performance of tasks (e.g., execution frequencies of LC tasks, response times and jitters of HC tasks) can be significantly improved under the ER schedulers when compared to that of the state-of-the-art EDF-VD scheduler.
How Does Machine Translation of User Interface Affect User Experience? A Study on Android Apps
(UTSA Department of Computer Science, 2015-09-22) Qin, Xue; Holla, Smitha; Wang, Xiaoyin; Huang, Liang
For global-market-oriented software applications, their user interfaces need to be translated to local languages to facilitate users from different areas in the world. A long-term practice in software industry is to hire professional translators or translation companies to perform the translation. However, due to the large number of user-interface labels and target languages, this is often too expensive for software providers, especially cost-sensitive providers such as personal developers of Android apps. On the other hand, more and more mature machine translation techniques are providing a cheap though imperfect alternative, and the Google Translation service has been widely used for translating websites and apps. However, the effect of translation quality of GUI labels on user experience has not been well studied yet. In this paper, we present a user study on 6 popular Android apps, to have 24 participants perform tasks on app variants with 4 different translation quality levels and 2 target languages: Spanish and Chinese. From our study, we acquire the following 3 major findings, including (1) although sharing only about 30% of GUI labels with the original localized versions, machine translated versions of GUI have similar user experience on most studied aspects, except a slightly lower task completion rate; (2) manually enhanced but still imperfect machine translated versions are able to achieve exact the same user experience in almost all studied aspects; and (3) users are not satisfied with the GUI of machine translated versions and the two major complaints are misleading labels of input boxes, and unclear translation of items in option lists.
Containerized SQL Query Evaluation in a Cloud
(UTSA Department of Computer Science, 2015-08) Zhang, Weining; Holland, David
Recent advance in cloud computing and lightweight software container technology opens up opportunities to execute data intensive applications where data is located. Noticeably, current database services offered on cloud platforms have not fully utilized container technologies. In this paper we present an architecture of a cloud-based, relational database as a service (DBaaS) that can package and deploy a query evaluation plan using light-weight container technology and the underlying cloud storage system. We then focus on an example of how a select-join-project-order query can be containerized and deployed in ZeroCloud. Our preliminary experimental results confirm that a containerized query can achieve a high degree of elasticity and scalability, but effective mechanisms are needed to deal with data skew.
Space-Time-Frequency Bag of Words Models for Capturing EEG Variability: A Comprehensive Study
(UTSA Department of Computer Science, 2015-01-02) Su, Kyung Min; Robbins, Kay A.
EEG data are multi-channel time-series recorded from the scalp surface to provide spatial and temporal measurements of brain signals. Because EEG headsets have varying channel numbers, channel placements, and sampling rates, EEG data may have different dimensions depending on the type of headset used for signal acquisition. These differences make it difficult to combine datasets for large-scale machine learning or data mining applications. Many traditional EEG features, including raw signal, are channel-specific [1], and not appropriate for processing multi-headset data of various channel configurations. Frame-based EEG features, which extract values from a field topography [2], [3], are less channel-specific. However, they usually assume that all EEG datasets are from the same headset. To represent EEG data regardless of headsets configurations, we have investigated several variations of the classical Bag-of-Words (BOW) model, a widely used technique to extract features from images for applications such as retrieval [4]. Images come in different sizes, shapes, and orientations. BOW approaches are effective in mapping such data to common feature sets. Traditional BOW models use a dictionary of local features based on key points and then construct a histogram of the occurrences of these features in an image. A disadvantage of BOW features is that they lose information about global spatial relationships of the key points in the image. However, this loss also makes the features robust to variations in scale and orientation. In this document, we describe several BOW approaches for EEG data that retain some frequency, spatial, and temporal relationships in EEG data. The proposed descriptors are relatively insensitive to the number of channels, channel placement, sampling rates, signal range, and subject response time. As a result, we can process EEG datasets of various configurations using a common dictionary of features. We have experimentally compared various approaches and parameters to provide an empirical basis for choosing optimal conditions. Section 2 describes the ideas of configuration independent EEG features based on BOW models, and Section 3 explains the implementation details and test results. Section 4 briefly discusses the implications of results for EEG analysis.
Sequence Diagrams Aided Security Policy Specification
(UTSA Department of Computer Science, 2014-12) Shen, Hui; Krishnan, Ram; Slavin, Rocky; Niu, Jianwei
A fundamental problem in the specification of regulatory privacy policies such as the Health Insurance Portability and Accountability Act (HIPAA) in a computer system is to state the policies precisely, consistent with their high-level intuition. In this paper, we propose UML Sequence Diagrams as a practical tool to graphically express privacy policies. A graphical representation allows decision-makers such as application domain experts and security architects to easily verify and confirm the expected behavior. Once intuitively confirmed, our work in this article introduces an algorithmic approach to formalizing the semantics of Sequence Diagrams in terms of Linear Temporal Logic (LTL) templates. In all the templates, different semantic aspects are expressed as separate, yet simple LTL formulas that can be composed to define the complex semantics of Sequence Diagrams. The formalization enables us to leverage the analytical powers of automated decision procedures for LTL formulas to determine if a collection of Sequence Diagrams is consistent, independent, etc. and also to verify if a system design conforms to the privacy policies. We evaluate our approach by modeling and analyzing a substantial subset of HIPAA rules using Sequence Diagrams.
Managing Security Requirements Patterns Using Feature Diagram Hierarchies
(UTSA Department of Computer Science, 2014-03) Slavin, Rocky; Lehker, Jean-Michel; Niu, Jianwei; Breaux, Travis D.
Security requirements patterns represent reusable security practices that software engineers can apply to improve security in their system. Reusing best practices that others have employed could have a number of benefits, such as decreasing the time spent in the requirements elicitation process or improving the quality of the product by reducing product failure risk. Pattern selection can be difficult due to the diversity of applicable patterns from which an analyst has to choose. The challenge is that identifying the most appropriate pattern for a situation can be cumbersome and time-consuming. We propose a new method that combines an inquiry-cycle based approach with the feature diagram notation to review only relevant patterns and quickly select the most appropriate patterns for the situation. Similar to patterns themselves, our approach captures expert knowledge to relate patterns based on decisions made by the pattern user. The resulting pattern hierarchies allow users to be guided through these decisions by questions, which elicit and refine requirements as well as introduce related patterns. Furthermore, our approach is unique in the way that pattern forces are interpreted as quality attributes to balance trade-offs in the resulting requirements. We evaluate our approach using access control patterns in a pattern user study.
Rethinking Security Requirements in RE Research
(UTSA Department of Computer Science, 2014-03) Hibshi, Hanan; Slavin, Rocky; Niu, Jianwei; Breaux, Travis D.
As information security became an increasing concern for software developers and users, requirements engineering (RE) researchers brought new insight to security requirements. Security requirements aim to address security at the early stages of system design while accommodating the complex needs of different stakeholders. Meanwhile, other research communities, such as usable privacy and security, have also examined these requirements with specialized goal to make security more usable for stakeholders from product owners, to system users and administrators. In this paper we report results from conducting a literature survey to compare security requirements research from RE Conferences with the Symposium on Usable Privacy and Security (SOUPS). We report similarities between the two research areas, such as common goals, technical definitions, research problems, and directions. Further, we clarify the differences between these two communities to understand how they can leverage each other’s insights. From our analysis, we recommend new directions in security requirements research mainly to expand the meaning of security requirements in RE to reflect the technological advancements that the broader field of security is experiencing. These recommendations to encourage cross-collaboration with other communities are not limited to the security requirements area; in fact, we believe they can be generalized to other areas of RE.
Energy-Efficient Scheduling of Primary/Backup Tasks in Multiprocessor Real-Time Systems (Extended Version)
(UTSA Department of Computer Science, 2013-10-30) Guo, Yifeng; Zhu, Dakai; Aydin, Hakan; Yang, Laurence T.
With the negative effects of the popular Dynamic Voltage and Frequency Scaling (DVFS) technique on transient faults being considered, the Primary/Backup approach has recently been exploited to save energy while preserving system reliability. In this paper, with the objectives of tolerating a single permanent fault and maintaining system reliability with respect to transient faults, we study energy-efficient dynamic-priority based scheduling algorithms for periodic Primary/Backup tasks on multiprocessor systems. Specifically, by separating primary and backup tasks on their dedicated processors, we first devise two schemes based on the idea of Standby-Sparing (SS): For Paired-SS, processors are organized as groups of two (i.e., pairs) and the existing SS scheme is applied within each pair of processors after partitioning tasks to the pairs. In Generalized-SS, processors are divided into two groups (of potentially different sizes), which are denoted as primary and secondary processor groups, respectively. The main (backup) tasks are scheduled on the primary (secondary) processor group under the partitioned-EDF (partitioned-EDL) with DVFS (DPM) to save energy. Next, instead of dedicating some processors to backup tasks, we propose schemes that allocate primary and backup tasks in a mixed manner to better utilize the slack time on all processors for more energy savings. On each processor, the Preference-Oriented Earliest Deadline (POED) scheduler is adopted to run primary tasks at scaled frequencies as soon as possible (ASAP) and backup tasks at the maximum frequency as late as possible (ALAP) to save energy. Online power management and recovery strategies are further discussed to address the problem with multiple permanent faults. Our empirical evaluations show that, for systems with a given number of processors, there normally exists an optimal configuration of primary and secondary groups for the Generalized-SS scheme, which leads to better energy savings compared to that of the Paired-SS scheme. Moreover, the POED-based schemes normally perform more stable and achieve better energy savings compared to those of the SS-based schemes.
A Framework for Composing Noninterferent Languages
(UTSA Department of Computer Science, 2013-09) Gampe, Andreas; von Ronne, Jeffery
Software is frequently implemented using multiple specialized languages for different tasks. Security type systems, one technique to secure software, have previously only been studied for programs written entirely in a single language. We present a framework that facilitates reasoning over composite languages. In it, guarantees of sufficiently related component languages can be lifted to the composed language. This can significantly lower the burden necessary to certify that such composite programs are safe. Our simple but powerful approach relies, at its core, on computability and security-level separability. Besides non-interference, we also show how the framework can accommodate notions of declassification. To demonstrate the applicability of this framework, we show that a standard secure while language from the literature satisfies all necessary requirements of a composition host, and sketch how to securely embed an expressive fragment of SQL.
Scheduling Algorithms for Elastic Mixed-Criticality Tasks in Multicore Systems (Extended Version)
(UTSA Department of Computer Science, 2013-06-10) Su, Hang; Zhu, Dakai; Mossé, Daniel
The Elastic Mixed-Criticality (E-MC) task model and an Early-Release EDF (ER-EDF) scheduling algorithm have been studied to address the service interruption problem for low-criticality tasks in uniprocessor systems, where the minimum service requirements of low-criticality tasks are guaranteed by their maximum periods. In this paper, focusing on multicore systems, we first investigate and empirically evaluate the schedulability of E-MC tasks under partitioned-EDF (P-EDF) by considering various task-to-core mapping heuristics. Then, to improve the service levels of low-criticality tasks by exploiting slack at runtime, with and without task migrations being considered, we study both global and local early-release schemes. Moreover, considering varied migration overheads between different cores, we propose the multicore-aware and migration constrained global-ER schemes. The simulation results show that, compared to the state-of-the-art Global EDF-VD scheduler, P-EDF with various partitioning heuristics can lead to many more schedulable E-MC task sets. Moreover, our proposed global and local ER schemes can significantly improve the execution frequencies (and thus service levels) of low-criticality tasks, while Global EDF-VD may severely affect them by discarding most of their task instances at runtime (especially for systems with more cores). Furthermore, by allowing task migrations, global-ER schemes can dramatically improve low-criticality tasks’ service levels for partitionings that do not balance high- and low-criticality tasks among the cores.
Preference-Oriented Scheduling Framework for Periodic Real-Time Tasks
(UTSA Department of Computer Science, 2013-05-15) Guo, Yifeng; Su, Hang; Zhu, Dakai; Aydin, Hakan
We consider a set of real-time periodic tasks where some tasks are preferably executed as soon as possible (ASAP) and others as late as possible (ALAP) while still meeting their deadlines. After introducing the idea of preference-oriented (PO) execution, we formally define the concept of PO-optimality. For fully-loaded systems (with 100% utilization), we first propose a PO-optimal scheduler, namely ASAP-ensured earliest deadline (SEED), by focusing on ASAP tasks where the optimality of tasks’ ALAP preference is achieved implicitly due to the harmonicity of the PO-optimal schedules for such systems. Then, for under-utilized systems (with less than 100% utilization), we show the discrepancies between different PO-optimal schedules. By extending SEED, we propose a generalized preference-oriented earliest deadline (POED) scheduler that can obtain a PO-optimal schedule for any schedulable task set. We further evaluate the proposed PO-optimal schedulers through extensive simulations. The results show that, comparing to that of the well-known EDF scheduler, the scheduling overheads of SEED and POED are higher (but still manageable) due to the additional consideration of tasks’ preferences. However, SEED and POED can achieve the preference-oriented execution objectives in a more successful way than EDF.
MOBBED (Mobile Brain-Body-Environment Decision-making) Part II: User Guide
(UTSA Department of Computer Science, 2013-04) Cockfield, Jeremy; Su, Kyung Min; Robbins, Kay A.
MOBBED is a database and MATLAB front end designed to facilitate the large scale analysis of multimodal event-rich data collections. MOBBED provides facilities for searching, querying, annotating, and caching of intermediate calculations. MOBBED can also be used with the MATLAB Parallel Processing Toolbox to take advantage of multicore desktops as well as clusters. These installation instructions assume that you will not be working with the Java source, but are using the JAR files that come with the distribution. The Java source, in the form of an Eclipse project, is available separately. [...]

Browse

Recent Submissions