Been busy this summer
I realize I’ve been neglecting my blog for the past few months but I have my reasons. Since I last posted I have gotten married, went on a honeymoon, and been busy with a full work and class load. I decided it was time to get back into the business of transcribing my thoughts on a semi-weekly (or bi-weekly) basis – so hear I am!
On the research front, Dr. Gamble and I have been working on a semantic model for denoting security requirements embedded in government standards documents. While we’ve been working on formalizing these security requirements for awhile now, we are now on the verge of a journal quality paper. I can’t spill the beans quite yet – but I can say it should have a fairly large impact in the world of government non-compliance analysis.
On the home front, Erin and I have finally settled in. Since June, we’ve organized and arranged the house to fit all of her stuff in and have been working both outside and in to improve the look and feel of the house. Outside we’ve torn up the grass, root and stump filled flower beds. In their place we’ve put Terracotta stones, a sprinkler system, fresh compost/dirt, weed fabric and mulch. It really is looking quite nice, although we have one more section to finish before the winter.
The weather is nice and the entropy of my life’s random variables seems relatively low right about now – which, after recent times, is quite nice. Good to be back!
ICSE 2011 Wrap up and future research work
After the long (16 hr) flight home from ICSE 2011, I see a full schedule of work, wedding, and house work. ICSE 2011 was a great first conference to go to. I had two great presentations, one at TEFSE and one at CSEE&T. The former was in regards to our traceability paper and the latter performance metrics. The experience at ICSE was much more than just about presentations. I had the pleasure to hang out with other great minds and network with other researchers from around the world.
While sitting in the Hilton Hawaiian bar and grill and reading a book, I had the surprising pleasure of an unexpected excellent conversation with some guys from NASA. I was reading the Foundation series by Isacc Asimov and enjoying a Malibu and pineapple when a group of three guys sat down nearby. They started talking about some obviously CS related topics like the latest on Oracle and Sun and one of them noticed my book. He said “that’s not John Gresham, are you here for ICSE?” Thus began a conversation with, as I found out through the course of the talk, someone who writes algorithms for the DSN (Deep Space Network) i.e. the network responsible for handling communication data from Voyager, Cassini, the Mars rovers and more. Given that I’m intensely interested in these things it was my pleasure to learn some of the nitty-gritty insider perspective.
This type of random encounter was, in my view, typical of my experience at ICSE. Everyone was mostly friendly and almost all had some passionate interest in their work. It was intellectually refreshing to take part in and now I’m motivated to move forward with the next phase of the security research. Dr. Gamble and I will be moving forward with a renewed sense of direction and some good grounding which I think will culminate in the next round of papers/reports for the AFOSR. This new initiative will be my work for the next two weeks in addition to my last minute wedding planning duties.
That’s it for now, stay tuned!
TEFSE’11 at the International Conference on Software Engineering
Today is the second day of the conference for me. Yesterday I participated in the workshop on secure systems. Now I’m switching gears into full SEREBRO mode. We kick off a three presentation streak today with my paper “Analyzing the Role of Tags as Lightweight Traceability Links,” continue tomorrow with our paper on performance indicators at CSEET and finally finish with a demonstration of SEREBRO to the entire conference on Friday.
Hawaii is beautiful outside, but I’m here 8-5 until at least Wed. I’ll post some lessons learned as I get some time when I get back. As for now, the keynote has begun – so I should go. Aloha!
Collision detection in Adobe Actionscript 3 (on a large scale)
It’s been a few weeks since I last worked on my VisGA, but I finally got some time this weekend. I was able to derive a relatively efficient collision detection scheme for path finding. Computational efficiency is a must with VisGA as cpu time and memory allocation are the two largest concerns for wide distribution of a flex/AC3 web app. The issue with actionscript is not that there are no methods for doing collision detection. Instead collision detection on multiple objects (10-100) which must be tested for each non-deterministically generated path between point A and point B can lead to serious computational overhead given adobe’s native collision testing methods.
For standard graphics objects, Actionscript provides two primary means of testing collisions.
First is the .hitTestObject – which allows you to compare a given graphics object, testSprite, to a point, testPoint, as in:
testSprite.hitTestPoint(testPoint)
My application needs to determine whether or not a line being drawn between two points (divided into N Manhattan segments) collides with an obstacle while trying to reach the destination point using non-deterministically selected heuristic driven path finding. Each segment must be tested as it is non-deterministically built to ensure that it does not collide with any previously placed obstacles. Using hitTestPoint would require P*M tests to be made for collision where P is the number of pixels between the “from” and “to” points on the segment and M is the number of obstacles to compare against. For anything but trivial cases this balloons very quickly for even a single segment if P or M is large. Considering there are N segments and L lines where L is the number of total start-end point pairs in the population, this is an exponentially large problem – just to collision test.
A much better option is the .hitTestObject – which allows you to compare a given sprite, mySprite (the segment in question), to another graphics object, testSprite. as in:
mySprite.hitTestObject(testSprite)
Using hitTestObject, I would need to do, at minimum, N*L hitTests and then further determine where exactly the collision is using boundary comparisons, so the total complexity would be 2N*L tests. While this is better it is still not ideal – ideally I would only need to do L computations with something like hitTestALL (which unfortunately doesn’t exist and is very non-trivial to implement).
I tinkered with ways to combine obstacle sprites into a sort of master sprite – but this causes the master sprite boundary box to be the smallest box which can surround all sprites rather than an irregular boundary box that only includes the component boundary box pixels. There is a work around for this by defining a custom boundary box – but this introduces other more difficult problems – such as where to go to when there is a collision (rectangular graphics objects provides a number of helpful points).
My ultimate thesis is a) Adobe should provide better collision detection for large numbers of items and b) the best way I’ve found to implement multiple collision testing and pathfinding is a complicated interplay of hitTestObject, iterated over all objects to be tested, boundary checking based on heuristics (such as knowing where you are coming from and testing only those sides of objects which may be in the path of such a vector), and finally optimized pathfinding logical heuristics that reduces the “internal loops” that can occur using non-deterministic pathfinding techniques.
Below is the core collision testing method for an array of obstacle items and a test_line generated from a “from” and “to” point using the graphics.drawPath method. It returns all obstacles that collide with the given line, subsequent analysis of exactly where the collision occurs and the logic used for routing around it is performed by the pathfinding algorithm:
protected function obstacle_collision(from:Point,to:Point):Array{
//checks for collision of the line formed between the two points "from" and "to" with all obstacles
var collision_array:Array = new Array();
var test_line:Line = new Line();
var test_line_sprite:Sprite = new Sprite();
test_line.commands.push(1,2);
test_line.coords.push(from.x,from.y,to.x,to.y);
test_line_sprite.graphics.drawPath(test_line.commands,test_line.coords);
//iterate through all obstacles and check for collision
for(var i:Number = 0;i < obstacles.length; i++){
if(obstacles[i].hitTestObject(test_line_sprite)){
collision_array.push(obstacles[i]);
}
}
return collision_array;
}
Hopefully this has clarified some nuanced issues regarding large scale collision testing. In my research I couldn’t find a simpler, more efficient way to do this. If you come across something better – let me know, otherwise feel free to reuse anything here for your purposes.
Cheers!
P.S. you can see the pathfinding in action in my latest version of VisGA available at: http://personal.utulsa.edu/~matt-hale/vis-ga/GA.html
Working on VisGA and next round of security research this week
On VisGA:
It has taken me a bit to get started again on non-house related projects post-spring break. Last week I started working on my VisGA again. I’m currently working on an efficient and complete algorithm for collision detection and re-routing of “pipes” that cross through obstacles. So far I’ve come up with a good algorithm for handling disjoint obstacles – but It needs to be extended for routing around merged obstacles (i.e. non-uniform obstacles composed of multiple squares). This is my main programmatic task for the next few days. Look for an updated VisGA version available via my utulsa web space in the next week or so.
Research Tasks:
On the other hand, I have a pile of papers and documents to look through to glean some insights regarding the next step for the Security Calculus work. I’m currently looking at the formal methods compliance and security assurance literature. The past few days I’ve been delving into the Common Criteria part 3 (CCpart3). This latest section of the CC seems to be much more applicable and boiled down for compliance and much more evaluation-directed than parts 1 and 2, which I looked at before for the SESS’11 paper.
As for the present its back to reading…
SESS’11 Program Announced
Our paper was submitted and accepted to the 7th International Workshop on Software Engineering for Secure Systems (SESS’11), part of ICSE’11, as a full paper. It involved a formal methods approach to system compliance verification using context unity with extensions to the standard formal semantics. Specifically we explore how a system can be verified against several security control statements, such as a self repudiation control, taken from the NIST SP800-53. The workshop program has been announced and I’m looking forward to attending!
Program available at:
http://homes.dico.unimi.it/~monga/program11.html
Our paper “Security Policy Foundations in Context Unity” available at:
CSEE&T Program announced
Our paper, Predicting Individual Performance in Student Project Teams, will be presented Tuesday May 24 in the 1:30-3:00 PM time slot as part of the Student performance evaluation and assessment (SPEA) portion of the CSEE&T conference.
SEREBRO as courseware provides a broad set of features targeted toward studying software engineering. Tied to these features are indicators that cue the instructor and team members as to their performance with respect to their collaboration, contribution, and progress toward stated milestones. We show that these indicators correlate to SME ratings of content and contribution of an individual in idea networks and to instructor project grades on work products associated with milestones. Thus, automatic SEREBRO assessment mechanisms are able to predict an individual’s grade and contribution to a project team.
We are currently pursuing additional types of analysis to examine an individual’s performance at filling particular roles on the team, such as lead, analyst, and programmer, and team dynamics over the project milestone period, such as how “bursty” vs. consistent communication relates to milestone success. We are interested in how performance indicators might be combined to yield real time predictions of impending build or challenge shortcomings. Our goal is to derive a weighted product which can be used to calculate an individual’s likelihood of failure given their progress towards milestone completion and mitigate that failure before it manifests itself. While we are several steps away from this, deriving performance metrics from existing real time system data lends support to our continued pursuit of performance classification.
Program information at:
http://conferences.computer.org/cseet/2011/CSEET_2011/Program.html#TU-3-1
For a paper preview go here:
