diff --git a/Android.bp b/Android.bp
index 9f508d5..a029265 100644
--- a/Android.bp
+++ b/Android.bp
@@ -1,15 +1,3 @@
-//
-// WARNING: Modifying this file will NOT automatically regenerate build.ninja.in!
-//
-// Before modifying this file make sure minibp is up to date:
-//    1) "repo sync build/soong" to make sure you have the latest build.ninja.in
-//    2) build minibp, which builds automicatically through the normal build steps. For example:
-//
-// After modifying this file regenerate build.ninja.in and build your changes:
-//    1) In your build directory, execute "../bootstrap.bash -r" to regenerate build.ninja.in
-//    2) Build again
-//
-
 subdirs = [
     "androidmk",
     "cmd/*",
@@ -168,6 +156,7 @@
         "blueprint-pathtools",
         "soong",
         "soong-android",
+        "soong-shared",
     ],
     srcs: [
         "genrule/filegroup.go",
@@ -233,6 +222,14 @@
     pluginFor: ["soong_build"],
 }
 
+bootstrap_go_package {
+    name: "soong-shared",
+    pkgPath: "android/soong/shared",
+    srcs: [
+        "shared/paths.go",
+    ],
+}
+
 //
 // Defaults to enable various configurations of host bionic
 //
diff --git a/android/config.go b/android/config.go
index 869a5c4..c3beb08 100644
--- a/android/config.go
+++ b/android/config.go
@@ -52,6 +52,10 @@
 	*config
 }
 
+func (c Config) BuildDir() string {
+	return c.buildDir
+}
+
 // A DeviceConfig object represents the configuration for a particular device being built.  For
 // now there will only be one of these, but in the future there may be multiple devices being
 // built
diff --git a/cmd/sbox/Android.bp b/cmd/sbox/Android.bp
new file mode 100644
index 0000000..fe4c7bb
--- /dev/null
+++ b/cmd/sbox/Android.bp
@@ -0,0 +1,21 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+blueprint_go_binary {
+    name: "sbox",
+    srcs: [
+        "sbox.go",
+    ],
+}
+
diff --git a/cmd/sbox/sbox.go b/cmd/sbox/sbox.go
new file mode 100644
index 0000000..ead3443
--- /dev/null
+++ b/cmd/sbox/sbox.go
@@ -0,0 +1,133 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package main
+
+import (
+	"fmt"
+	"io/ioutil"
+	"os"
+	"os/exec"
+	"path"
+	"path/filepath"
+	"strings"
+)
+
+func main() {
+	error := run()
+	if error != nil {
+		fmt.Fprintln(os.Stderr, error)
+		os.Exit(1)
+	}
+}
+
+var usage = "Usage: sbox -c <commandToRun> --sandbox-path <sandboxPath> <outputFiles>"
+
+func usageError(violation string) error {
+	return fmt.Errorf("Usage error: %s.\n %s", violation, usage)
+}
+
+func run() error {
+	var outFiles []string
+	args := os.Args[1:]
+
+	var rawCommand string
+	var sandboxesRoot string
+
+	for i := 0; i < len(args); i++ {
+		arg := args[i]
+		if arg == "--sandbox-path" {
+			sandboxesRoot = args[i+1]
+			i++
+		} else if arg == "-c" {
+			rawCommand = args[i+1]
+			i++
+		} else {
+			outFiles = append(outFiles, arg)
+		}
+	}
+	if len(rawCommand) == 0 {
+		return usageError("-c <commandToRun> is required and must be non-empty")
+	}
+	if outFiles == nil {
+		return usageError("at least one output file must be given")
+	}
+	if len(sandboxesRoot) == 0 {
+		// In practice, the value of sandboxesRoot will mostly likely be at a fixed location relative to OUT_DIR,
+		// and the sbox executable will most likely be at a fixed location relative to OUT_DIR too, so
+		// the value of sandboxesRoot will most likely be at a fixed location relative to the sbox executable
+		// However, Soong also needs to be able to separately remove the sandbox directory on startup (if it has anything left in it)
+		// and by passing it as a parameter we don't need to duplicate its value
+		return usageError("--sandbox-path <sandboxPath> is required and must be non-empty")
+	}
+
+	os.MkdirAll(sandboxesRoot, 0777)
+
+	tempDir, err := ioutil.TempDir(sandboxesRoot, "sbox")
+	if err != nil {
+		return fmt.Errorf("Failed to create temp dir: %s", err)
+	}
+
+	// In the common case, the following line of code is what removes the sandbox
+	// If a fatal error occurs (such as if our Go process is killed unexpectedly),
+	// then at the beginning of the next build, Soong will retry the cleanup
+	defer os.RemoveAll(tempDir)
+
+	if strings.Contains(rawCommand, "__SBOX_OUT_DIR__") {
+		rawCommand = strings.Replace(rawCommand, "__SBOX_OUT_DIR__", tempDir, -1)
+	}
+
+	if strings.Contains(rawCommand, "__SBOX_OUT_FILES__") {
+		// expands into a space-separated list of output files to be generated into the sandbox directory
+		tempOutPaths := []string{}
+		for _, outputPath := range outFiles {
+			tempOutPath := path.Join(tempDir, outputPath)
+			tempOutPaths = append(tempOutPaths, tempOutPath)
+		}
+		pathsText := strings.Join(tempOutPaths, " ")
+		rawCommand = strings.Replace(rawCommand, "__SBOX_OUT_FILES__", pathsText, -1)
+	}
+
+	for _, filePath := range outFiles {
+		os.MkdirAll(path.Join(tempDir, filepath.Dir(filePath)), 0777)
+	}
+
+	cmd := exec.Command("bash", "-c", rawCommand)
+	cmd.Stdin = os.Stdin
+	cmd.Stdout = os.Stdout
+	cmd.Stderr = os.Stderr
+	err = cmd.Run()
+	if exit, ok := err.(*exec.ExitError); ok && !exit.Success() {
+		return fmt.Errorf("sbox command %#v failed with err %#v\n", cmd, err)
+	} else if err != nil {
+		return err
+	}
+
+	for _, filePath := range outFiles {
+		tempPath := filepath.Join(tempDir, filePath)
+		fileInfo, err := os.Stat(tempPath)
+		if err != nil {
+			return fmt.Errorf("command run under sbox did not create expected output file %s", filePath)
+		}
+		if fileInfo.IsDir() {
+			return fmt.Errorf("Output path %s refers to a directory, not a file. This is not permitted because it prevents robust up-to-date checks", filePath)
+		}
+		err = os.Rename(tempPath, filePath)
+		if err != nil {
+			return err
+		}
+	}
+	// TODO(jeffrygaston) if a process creates more output files than it declares, should there be a warning?
+	return nil
+}
diff --git a/genrule/genrule.go b/genrule/genrule.go
index 2ff018f..b98ccfd 100644
--- a/genrule/genrule.go
+++ b/genrule/genrule.go
@@ -16,11 +16,14 @@
 
 import (
 	"fmt"
+	"path"
 	"strings"
 
 	"github.com/google/blueprint"
 
 	"android/soong/android"
+	"android/soong/shared"
+	"path/filepath"
 )
 
 func init() {
@@ -32,6 +35,10 @@
 	pctx = android.NewPackageContext("android/soong/genrule")
 )
 
+func init() {
+	pctx.HostBinToolVariable("sboxCmd", "sbox")
+}
+
 type SourceFileGenerator interface {
 	GeneratedSourceFiles() android.Paths
 	GeneratedHeaderDirs() android.Paths
@@ -42,7 +49,11 @@
 }
 
 type generatorProperties struct {
-	// command to run on one or more input files.  Available variables for substitution:
+	// The command to run on one or more input files. Cmd supports substitution of a few variables
+	// (the actual substitution is implemented in GenerateAndroidBuildActions below)
+	//
+	// Available variables for substitution:
+	//
 	// $(location): the path to the first entry in tools or tool_files
 	// $(location <label>): the path to the tool or tool_file with name <label>
 	// $(in): one or more input files
@@ -51,9 +62,8 @@
 	// $(genDir): the sandbox directory for this tool; contains $(out)
 	// $$: a literal $
 	//
-	// DO NOT directly reference paths to files in the source tree, or the
-	// command will be missing proper dependencies to re-run if the files
-	// change.
+	// All files used must be declared as inputs (to ensure proper up-to-date checks).
+	// Use "$(in)" directly in Cmd to ensure that all inputs used are declared.
 	Cmd string
 
 	// Enable reading a file containing dependencies in gcc format after the command completes
@@ -164,7 +174,7 @@
 		}
 	}
 
-	cmd, err := android.Expand(g.properties.Cmd, func(name string) (string, error) {
+	rawCommand, err := android.Expand(g.properties.Cmd, func(name string) (string, error) {
 		switch name {
 		case "location":
 			if len(g.properties.Tools) > 0 {
@@ -175,14 +185,26 @@
 		case "in":
 			return "${in}", nil
 		case "out":
-			return "${out}", nil
+			return "__SBOX_OUT_FILES__", nil
 		case "depfile":
 			if !g.properties.Depfile {
 				return "", fmt.Errorf("$(depfile) used without depfile property")
 			}
 			return "${depfile}", nil
 		case "genDir":
-			return android.PathForModuleGen(ctx, "").String(), nil
+			genPath := android.PathForModuleGen(ctx, "").String()
+			var relativePath string
+			if path.IsAbs(genPath) {
+				var err error
+				outputPath := android.PathForOutput(ctx).String()
+				relativePath, err = filepath.Rel(genPath, outputPath)
+				if err != nil {
+					panic(err)
+				}
+			} else {
+				relativePath = genPath
+			}
+			return path.Join("__SBOX_OUT_DIR__", relativePath), nil
 		default:
 			if strings.HasPrefix(name, "location ") {
 				label := strings.TrimSpace(strings.TrimPrefix(name, "location "))
@@ -201,8 +223,16 @@
 		return
 	}
 
+	// tell the sbox command which directory to use as its sandbox root
+	sandboxPath := shared.TempDirForOutDir(android.PathForOutput(ctx).String())
+
+	// recall that Sprintf replaces percent sign expressions, whereas dollar signs expressions remain as written,
+	// to be replaced later by ninja_strings.go
+	sandboxCommand := fmt.Sprintf("$sboxCmd --sandbox-path %s -c %q $out", sandboxPath, rawCommand)
+
 	ruleParams := blueprint.RuleParams{
-		Command: cmd,
+		Command:     sandboxCommand,
+		CommandDeps: []string{"$sboxCmd"},
 	}
 	var args []string
 	if g.properties.Depfile {
diff --git a/shared/paths.go b/shared/paths.go
new file mode 100644
index 0000000..f5dc5ac
--- /dev/null
+++ b/shared/paths.go
@@ -0,0 +1,26 @@
+// Copyright 2017 Google Inc. All rights reserved.
+//
+// Licensed under the Apache License, Version 2.0 (the "License");
+// you may not use this file except in compliance with the License.
+// You may obtain a copy of the License at
+//
+//     http://www.apache.org/licenses/LICENSE-2.0
+//
+// Unless required by applicable law or agreed to in writing, software
+// distributed under the License is distributed on an "AS IS" BASIS,
+// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+// See the License for the specific language governing permissions and
+// limitations under the License.
+
+package shared
+
+// This file exists to share path-related logic between both soong_ui and soong
+
+import (
+	"path/filepath"
+)
+
+// Given the out directory, returns the root of the temp directory (to be cleared at the start of each execution of Soong)
+func TempDirForOutDir(outDir string) (tempPath string) {
+	return filepath.Join(outDir, ".temp")
+}
diff --git a/ui/build/Android.bp b/ui/build/Android.bp
index 25520da..489c06d 100644
--- a/ui/build/Android.bp
+++ b/ui/build/Android.bp
@@ -18,6 +18,7 @@
     deps: [
         "soong-ui-logger",
         "soong-ui-tracer",
+        "soong-shared",
     ],
     srcs: [
         "build.go",
diff --git a/ui/build/build.go b/ui/build/build.go
index 83dbcb6..1400c48 100644
--- a/ui/build/build.go
+++ b/ui/build/build.go
@@ -125,6 +125,8 @@
 
 	checkCaseSensitivity(ctx, config)
 
+	ensureEmptyDirectoriesExist(ctx, config.TempDir())
+
 	if what&BuildProductConfig != 0 {
 		// Run make for product config
 		runMakeProductConfig(ctx, config)
diff --git a/ui/build/config.go b/ui/build/config.go
index 7e8091b..16826f2 100644
--- a/ui/build/config.go
+++ b/ui/build/config.go
@@ -21,6 +21,8 @@
 	"runtime"
 	"strconv"
 	"strings"
+
+	"android/soong/shared"
 )
 
 type Config struct{ *configImpl }
@@ -250,6 +252,10 @@
 	return filepath.Join(c.OutDir(), "soong")
 }
 
+func (c *configImpl) TempDir() string {
+	return shared.TempDirForOutDir(c.SoongOutDir())
+}
+
 func (c *configImpl) KatiSuffix() string {
 	if c.katiSuffix != "" {
 		return c.katiSuffix
@@ -306,7 +312,7 @@
 }
 
 // RemoteParallel controls how many remote jobs (i.e., commands which contain
-// gomacc) are run in parallel.  Note the paralleism of all other jobs is
+// gomacc) are run in parallel.  Note the parallelism of all other jobs is
 // still limited by Parallel()
 func (c *configImpl) RemoteParallel() int {
 	if v, ok := c.environ.Get("NINJA_REMOTE_NUM_JOBS"); ok {
diff --git a/ui/build/util.go b/ui/build/util.go
index 37ac6b9..2555e8a 100644
--- a/ui/build/util.go
+++ b/ui/build/util.go
@@ -50,6 +50,19 @@
 	}
 }
 
+// ensureEmptyDirectoriesExist ensures that the given directories exist and are empty
+func ensureEmptyDirectoriesExist(ctx Context, dirs ...string) {
+	// remove all the directories
+	for _, dir := range dirs {
+		err := os.RemoveAll(dir)
+		if err != nil {
+			ctx.Fatalf("Error removing %s: %q\n", dir, err)
+		}
+	}
+	// recreate all the directories
+	ensureDirectoriesExist(ctx, dirs...)
+}
+
 // ensureEmptyFileExists ensures that the containing directory exists, and the
 // specified file exists. If it doesn't exist, it will write an empty file.
 func ensureEmptyFileExists(ctx Context, file string) {