Below is an overview of recent (2016) computing & networking research advances handpicked from presentations during USC Viterbi School of engineering Events. Presentations were carried by the researchers themselves.
Most technologies solutions presented are integrated by the GAFA’s, and for a good part, tech venture have been started to market them.
Articles below written by Dan Landau.
Vulnerabilities of Encrypted Databases
Safeguarding privacy in genomic research using cryptography
Improving web links using server logs
Using social networks to predict feelings
Improving Data Center Reliability
Autonomous mobile robots navigation in urban environments
Muhammad Naveed, U. Illinois
Attention, data from encrypted medical records can be revealed !
Sensitive data like hospital records can be securely stored in state of the art encrypted databases systems, like CryptDB. CyptDB is an encrypted database systems that supports SQL queries.
Nonetheless, a key restriction is that all cryptography techniques must do a tradeoff between security and practicality. There is an inherent contradiction between the need to to secure the data, hide it, one one side, but also allow it to be effciently accessible, searchable on the other side.
Bottom line is that the efficiency of cipher techniques is hampered by the needs to execute operations, e.g. database searches, on the encrypted data.
For example, encrypted medical records hide sensitive information things like names, medical conditions, dates in hospitals.
However, secured medical information systems must still be able to access and search this data. To satisfy this, standard cipher mechanisms maintain properties of the original data.
Typically the ciphered data preserves the order of the original data. Thus one can search the ciphered records efficiently using existing database queries.
More secure cypher techniques that ignore the structure of the original data exists : however, they are not used in existing database systems. Not only efficient implementations of operations would be difficult, but it would also require re-engineering existing implentations.
These existing state of the art mechanisms, called PPE - Property Preserving Encryption, preserve original data attributes like order or frequency. The problem is that this is precisely what makes them vulnerable to inference attacks using publicly available auxiliary data. Easy to reach sources like census data, language statistics. A wealth of informations.
In our medical example, census data provides the distribution of familly names. And first names.
Armed with these infos, one can now identify the full name of the ciphered records by comparing their frequency distribution.
Research shows that, state of the art encrypted database systems are vulnerable to those attacks, and it is often possible to recover 90% of some attributes !
Notes :
Muhammad Naveed UIUC naveed2@illinois.edu
Seny Kamara Microsoft Research senyk@microsoft.com
Charles V. Wright Portland State University
Muhammad Naveed, U. Illinois
A new encryption mechanisms enables sharing of sensitive genomic information while guaranteeing privacy.
Research on genes and their effect on medical conditions is a promising topic. However, publicly sharing one’s genome is a sensitive matter. Security mechanisms must provide a solution to this problem.
An immediate approach could be for for each patient to privately share this genome with a given researcher : unfortunately, is restrictive, does not scale, and is prone to abuse.
Such occurrence took place when an Indian tribe volunteered to share their genome for diabetes research : ultimately the data was used to study migration, inbreeding and schizophrenia.
Cryptography can provide a solution.
One approach is to use Functional Encryption (FE). FE can be used to automatically share genomic data to be used for a specific research. In FE, a user receives from a trusted authority an encryption key specific to the genetic function that will be executed by the researcher. This ensures only the agreed research can be carried on the user’s data.
However this scheme has important flaws. The ciphering used is extremely unefficient (this is large complex genome data). These techniques are not fully validated yet. Furthermore, it restricts the research to a specific computing function. Unflexible. Finally, preventing computing of the same function on an other data requires additional cipher mechanisms and complexity.
A better solution is to use Controlled Functional Encryption (CFE). In CFE, the user’s data is not restricted to a specific function : it is rather controlled by a policy. This scheme is more flexible, more efficient and can scale.
In CFE, the user defines a policy, a parameter set, that controls how its data can be used. This policy is uploaded to a trusted authority. He also receives from the trusted authority a key for encrypting its data. The key will be used to encrypt the data when publishing its data (e.g. sending it to a researcher).
But the important novelty here is that the client (e.g. a researcher) will need to obtain a key from the trusted authority to compute research on the user’s encrypted data. This key will only work for a given function, and will only be returned if the researcher’s topic fits the user’s defined defined policy.
This mechanisms provides a flexible implementation supporting multiple research areas and maintains the user’s privacy restrictions.
The encryption is proven to be efficient and enables large scale genome encryption.
Muhammad Naveed, Shashank Agrawal , Manoj Prabhakaran, Carl A. Gunter - University of Illinois at Urbana-Champaign
Xiaofeng Wang - Indiana University Bloomington
Erman Ayday, Jean-Pierre Hubaux - École polytechnique fédérale de Lausanne
Robert West U. Stanford
Server logs contains a wealth of information regarding user behavior. Especially, we can understand how they find content, - easily with a couple of clicks or by following multiple cum bersome links ? By learning usage patterns, we can identify what links are unsued, which ones are popular and even better estimate what are the optimal links for a given page. We can do the later by identifying missing links.
Searching for information online is based on links that points the user towards the targeted content. The choice of which links are included in a given page is essential : the links control how easily will user find the desired information.
The tasks of editing and maintaining those links is left to human editors who decide what are relevant links to be included for a given page. This can be a complex task. Consider the case of Wikipedia containing 5 Million articles, 7000 new articles per day, from about 12000 editors.
Unfortunately observed user behavior statistics, obtained from simple server logs parsing, shows that a great part of included links are irrelevant : only about ⅓ of of links are used in a given month. That means ⅔ of links were unused ! Amongst the visited links, for a given month, only about 1% were used more than 100 times.
The statistics are clear : an important portion of links are not relevant the users.
The proposed solution is to use the user behavior statistics to optimize the links returned for a given page/request.
Server logs traffic statistics immediately enables us to identify the high traffic links for a given pages. Those are the most relevant links. But wen can learn more, we can can attempt to learn what would the optimal links be.
Actually, traffic statistics can indicate what pages are simply used as stepping stones towards a target page. If we observe a recurring pattern of (multiple) indirect navigational path leading from a given source to a target, we have detected a missing link. We can then consider adding this direct link from the source to the target : this will speed up user access to content by reducing its number of stepping stones pages.
To identify those missing links, we use a probability model describing the chances of navigation from one page to another. By parsing server logs, based on the statistics from page navigation sequences observed during all user sessions, we build a probabilistic model : a heuristic graph tree that contains the probability of reaching pages for every page. This key computing factor here is evaluating the probability of reaching a target page from a given source page considering other existing links.
The model takes into account the law of diminishing returns : the more links already existing on given page, the less click rate we will get for an additional link. The more links, the less returns. This feature also matches with the limits on user’s user’s visual focus : the number of links must be limited, we can not add all direct links to all pages !
Statistics also confirm that link order is also improvement : links placed higher have a higher in the page click rate.
The algorithm can now scan the graph tree and extract from it the most promising links that are not already included. : the missing links with the highest rate of clickthrough probability.
As each identified missing link must be approved by an editor, for budget constraints, we limit the algorithm to the best K links.
This predictive model, validated on existing traffic statistics, enables us to return the list of of K best links for the site. This optimal list of links can then be automatically suggested to article editors through a simple user interface.
The addition of suggested links, learned from user’s behavior, shows a high usage rate, meaning faster access to information.
In a month, the algorithm’s 10000 best links generated a click volume of 300,000.
The usage of these 10,000 links suggested by the algorithm, averaging 30 clicks per link, must be compared with the 500,000 links added by humans that were entirely unused.
The new links used as much as the top visited links defined by the human editors, thus increasing the total number of high traffic links.
Proving this approach is an excellent complement to the editors work.
This link system could be further improved using machine learning statistics from user behavior. The links would then continuously adapt to the observed to user behavior.
The approach is generic and can be applied to any site with a large content
Comments :
Ashwin Paranjape, Stanford University
Robert West, Stanford University
Leila Zia, Wikimedia Foundation
Jure Leskovec, Stanford University
By Robert West
We can use social networks data to predict sentiment between two persons. Traditionally, this analysis is either based on network structure or on messages exchanged.
When using network structure, we can use social theories to guess sentiments.
For example balance theory predicts that friends of my friends are my friends. Similarly, enemies or my enemies are my enemies. If A is a friend of B, then B is a friend of A, and both A and B are friends.
Another approach is to parse messages exchanged : we infer sentiments from the semantics associated with words tokens obtained.
We can improve the prediction by building a new hybrid heuristic approach that combines both the logic of social theories from network structure and the interpretation of text messages.
This approach allows to better detect ironic messages that actually are sign of positive relationship.
The model built is trained on social networks from wikipedia administration votes and from US congress votes.
Results prove that this hybrid approach performs better than network-only or text-only predictions. This approach takes advantage of what data is available, whether it be a dense network structure, or rather important exchange of messages.
Comments :
Robert West, Hristo S. Paskov, Jure Leskovec, Christopher Potts - Standford University
By Vincent Liu, U. Washington
Network topology, wiring, and software solutions resolving data center’s edge router bottlenecks.
Data center operators face a serious technical challenges : the continuous increase in network capacity demand.
This demand is driven by user growth, new techniques such as higher capacity servers, kernel bypass, and higher network demand from applications. Google reports that it has been doubling its bi-section bandwidth (bandwidth at the narrowest part of the network) capacity practically every recent years. Networks are a large and growing cost of data centers. Especially because, applications are highly sensitive to tail latencies, network must be dimensioned for peak usage. Consequently average usage is low further increasing the costs.
Operators respond by adding capacity incrementally in order to maintain existing services. Increasing the quantity of network hardware and switches.This leads to increased wiring complexity.
Current network topology is based on a clos network layer of core switches, aggregation switches and finally Top-Of-Rack switches connecting to dozens of servers.
Some existing issues are growing inter-rack edge communication to support jobs too large for a single rack.
Server correlation is also an issue : often a rack is dedicated to a service. e.g. Facebook rolls out a rack entirely dedicated to MemCache and Front-End web. This is an issue, as it implies all the servers will get hot at the same time. It will also more pressure on the Tor switch as traffic increases.
Also, in existing architecture, Tor switches are single point of failure compromising the entire rack of servers.
The subway approach is a practical and efficient wiring solution enables to easily increase capacity, and reliability without the costly need for rewiring.
Firstly, add overlapping wiring from servers to the adjacent racks Tor switches.This efficiently increases edge network capacity, relieving thus an important network burden, by improving neighbouring racks communication that bypasses the congested core switches. Adjacent rack communications are growing due to the advent of jobs too large for a single rack.
Secundly, add overlapping wiring from between adjacent aggregation switches. This improves redundancy and especially enables short path failure recovery avoiding core switches in edge to edge communications.
For practical reasons, we can also add a new Tor at the bottom of the rack, thus enabling improved connectivity.
Failure recovery is a key data center issue as commodity hardware is used for costs and scalability reasons : in return, due to the large number of equipments, and due to the insufficient router availability standards failures are continuously occurring.
Failure recovery can be further increased (~ms)aggressively monitoring connectivity using hearbeats : this enables establishment of recovery paths before retransmits are necessary. Additional improvements could be made through similar hardware mechanisms.
The new connectivities also gives more flexibility in clustering servers.
Increasing server to Tor connectivity improves load balancing capacities : we can design adaptative load balancing based on new improved weight based routing algorithms, that will distribute load across available tors thus improving performance and reliability. This is good response to overheating oversubscribed Tor switches.
To respond to intermittent, undetected individual packet drops, new alogorithms are presented providing fine grain detection packet monitoring and send gather statistics enable routing corrections.
Note that the subway wiring approach only applied to the edge network and can be applied independently of the core network topology.
Comments :
Vincent Liu, Danyang Zhuo, Simon Peter, Arvind Krishnamurthy, Thomas Anderson - U. Washington
By Giuseppe Loianno
Navigation solution to enabling autonomous flights and cooperations between micro aerial vehicle (MAV) using consummer electronics !
MAV refers to flying robots lsmaller than a meter and measuring a maximum of a kg or so. Costs varies in the $1000 - 10000 range.
Physical dynamics make the control of autonomous robots flights extremely difficult. Localisation is a key challenge. Especially in the absence of GPS or motion capture sensors.
Existing on-board sensors are very slow compared to possibilities offered by motion capture.
IMU only sensing is fast, but noisy. Motion capture is easy with commodities camera, but algorithm are costly (cpu power). A satisfying solution, Visual Inertial Odometry, is to fuse both sensor signal : from the motion capture and IMU inertia sensors.
Such sensors, are available on today’s smartphones : regrouping a number of sensor, communication, navigation and computing capacities, they offer a cheap and practical solution to control the flights of MAV. The initial project was completed using a special phone Tango developped by google especially for 3D mapping.
By using cheap infrared projection and camera (RGB-D as used in Microsoft Kinect), robots can realize 3D Maps. This technique measures the disturbance observed in the structured light projection and allows to estimate depth.
Based on physical observations, position, and intended trajectory, the controller commands the rotors and ensure the flights. The vehicle is able to recognize and avoid obstacles. Sampling and control is done at up to 200Hz. Current COTS cpu’s computing capacity is amply sufficient. Speed is around a meters per second.
The model presented here uses commonly available quadrotor platform.
The vehicle is able to respond to unexpected perturbations and regain its intended trajectory.
Even better : we can now fly a swarm of robots ! In this case, a ground station will be the main controller. Robots can be used to map an indoor environment. . The ground station will then merge maps information from each MAV. e.g. Emergency situation. Another example is to collaborate for a surveillance mission. A solution is presented that optimizes the trajectory of each vehicle : based on relative localization, it maximizes the objectives - e.g. coverage area - while guaranteeing collision avoidance.
Further developments :
The mass production of sensors, network equipment, chips is continuously leading towards cheaper and more efficient components. This era of the industrial internet, enables a new era in robotics. Leveraging this ubiquitous hardware along with open source software solutions opens up multiple economical applications (as opposed to the military field). Existing applications include search and rescue, 3D mapping, surveillance, construction.
Comments :
[ Flying Smartphones : Automated flight enabled by consummer electronics IEEE Robotics & Automation June 2015 ]
[Autonomous deployment of swarms of micro-aerial vehicles in cooperative surveillance]
Martin Saska, Jan Chudoba, Libor Pˇreucil, Justin Thomas, Giuseppe Loianno, Adam Tˇresˇnˇak´, Vojtech Von ˇ asek ´and Vijay Kumar
[Flying Robots: Fast Autonomous Navigation and Physical Interaction]
Presentation at University of Southern California, February 2016
By Chin-Kai Chang, USC
How do robots navigate ? Deep learning outperforms traditional arithmetic approaches !
Mobile service robots are already common in assiting humans in multiple areass, industry, warehouses, medical, search & rescue, mars explotation, policement, military situations.
They must be fully autonomous mobile platform able to operate in unrestricted environments.
Navigation problems can be categorized in :
Urban navigation is a complex problem relying on real time vision algorithms to detect moving (human, vehicles,...), static obstacles (buildings, walls, …). Occluded obstacles. The navigation algorithm must identify unmarked path from the camera’s images, obtained at about 10fps. Milliseconds reactions decision are required to avoid accidents. Robustness is also key for safety. For example, support variable light conditions and shadows. Handle complex images harbouring a multitude of disparate shapes. In addition vision algorithm must recompute the environment from continuously changing images (of the same setting) as the robot is moving. The algorithm must what looks image variations dues to its own movement, versus actual changes in the environment.
Vision is also used for localization when GPS signal is denied.
Autonomous robots must solve two essential problems :
Localization is based on identifying and memorizing landmarks to enable the construction of maps by association.
The main navigation functions are : fused odometry (sensor data aggregation), occupancy map (obstacles), road recognition, and path planning.
For road recognition, previous state of the art algorithm analyze a 2D image’s gist and saliency, and identify the path’s edge lines running towards the vantage point : the point in the horizon at the center of the road, i.e. the navigation target.
Visual processing is based on two related essential image computation : saliency and gist. The saliency refers to the distinctiveness of an image area. Our brain, and robots’, compute visual elements serially, to limit computing complexity and maintain speed of reaction. They use saliency to idenfity which elements must be processed first : the most relevant ones.
The gist is a computation based on local gradient (scale and orientation) information of the image : it provides a rough description (the gist) of the scene.
For improved robustiness and accuracy, this novel algorithm uses several images, each with different orientations and scales, and computes an average image. techniques presented above and applied to
In our case, path and vantage point recognition is based on both image structure or color. Using color, the algorithms tries detects boundaries : A kalman filter enables the segmentation of the image in in different areas, thus revealing the path. The robots knows to look for the path on the ground and thus can eliminate the sky area. The algorithm seeks to identify the road color and uses this to remain on it.
Another strategy is to to identify the road area is texture. This is difficult to analyze and requires estimations. A Gabor filter, a type of filtering used in in human vision, enables the selection of confidence pixels that accurately describe the texture.
Once the path is identified.
In existing algorithms, the vantage point is identified by search for the biggest triangle that can fit into the path area. Here, each confidence pixels votes for a sample of vantage points candidates. To reduce computing complexity, the sampling is dense in the pixels near the previous vantage point, and sparse in the rest of the image(less chances of finding a good VP).
The VP selection is further validated by verifying no borders are found it and towards the vehicle. Ensuring the line is clear.
This algorithm enables the robot to navigate for a few hundred meters in an open flat environment but shows some limitations.
The road recognition algorithm is further improved by a new approach based on path edge identification. First, compute the image’s edge lines. Then extract the road lines, removing lines that are not part of the horizontal plane. Use these segments to vote for the VP : the road line segments point toward the VP. The algorithm makes correction for the robot movement, e.g. lateral movements, allowing it to stay directed to the VP. This approach enables the robot to navigate several km (>5km) amongst a crowd of pedestrian obfuscating the horizon view. The robot is enable can distinguish road lines around him despite the crowd.
Still relying only on monocular camera images, this approach does not assume a triangular road shape, is able to handle complex shapes, textures, shadows and crowds.
Nevertheless, for real life applications in complex environments, proposed algorithms, despite proven improvements remain vulnerable. The next improvement is : DeepVP learning. Deep learning, based on convolution neural networks has already shown major improvement in object recognition (60%!), and also in segmentation and contour detection.
Here we sue the existing 1M VP image dataset from Google’s streetview. For each image, the VP is easily computed from the available pitch and heading information. The dataset is split into 75% training images and 25% testing.
Deep learning is proven to considerably outperforms all existing handcrafted approaches. On the available dataset, the DeepVP shows 92% performance versus 47% for the traditional algorithms discussed above. Speed is also improved by 30 times. Statistics proves the DeepVP shows a robust, uniform higher accuracy in VP identification versus traditional alogorithms subject to error under complex unexpected conditions (e.g. shadows, etc..)
The prototype is built using a wheel chair base with a 16 2GHz core : high performance computing. Multiple vision sensors cameras are used : 3D 360 velodyne, laser range sensor, 2D stereo, IR depth camera. It also uses an IMU to detect acceleration.
Navigation & built-in obsctacle avoidance technologies, enable the prototype is successfully able to navigate at walking speed finds its way through a campus area while avoiding moving pedestrians, vehicles, bicyles, etc.
Chin-Kai Chang