Homework 1

[-w]

Expressing formulas in Photoshop blend modes

Background

It should have been trivial to remove microstock watermarks with Photoshop (especially when the watermarks are applied in a very predictable way), but it hasn’t been.

When I was in high school, I spent no less than a week reading about Porter-Duff alpha composition and solving linear equations just to come up with a mathematical result on how I should remove a watermark given watermarked versions of known images. After that, I had no idea how to implement it in an easy-to-use way. I mean, sure Photoshop has a wide variety of blend modes and filters that obviously use math in the end, but what formulas did they use, and how could I compose them to evaluate the equation I derived?

I ended up writing a script to do it outside of Photoshop. It wasn’t until I was a sophomore in college that I found a listing of what formulas blend modes use and figured out a way to get this done inside Photoshop.

Problem Statement

The goal is to synthesize an arrangement of layers (including source data and blend mode) and a list of filtering steps (including what filter, target layer, and parameters) that result in the computation of a given expression on each pixel. For simplicity, each output pixel shall be a function of pixels at the exact same coordinate from each input image
(i.e., it won’t synthesize something like flipping an image)

I have a few ideas on why these “programs” are hard to write manually for most users:

1. They don’t have a precise understanding of the blend modes and filters
2. Programmers are used to working with simple building blocks, but these blend modes and filters usually do a number of operations, and single operations usually aren’t available

Specification

First, I’d like to get the output (described in problem statement) given a mathematical formula.

Second, it would be useful to be able to come up with a formula given example input-output pairs. Since we consider each pixel coordinate independently, a single image provides several input-output pairs. For the case of microstock theft, it should make it really easy to solve the resulting equation for the input given the output (using some existing computer algebra system) and then asking for an implementation with blend modes.

[Matthew E. Torok]

Hi all,

Attached find a PDF of my results for homework 1. Emailing it out to the list, as instructed.

I should note here that I realize I am a bit hand-wave-y in part 3. Specifically, I am vague on how to go from my proposed graphical spec to a precise input for a synthesizer to solve. Partly, this is because Ras instructed us in class that we should focus on the abstract concept of what information we want to share with the spec, rather than the precise nature of how the spec should be expressed. But also partly this is because doing this seems like a Hard Problem(TM), or at least I have no easy answer for it. Hopefully, that won't be true by the end of the course :)

Feedback is appreciated.

Thanks!

-Matt

--
 
 

[Sarah Chasins]

Like Matt, I'd love to hear feedback!

-Sarah

Background

Many library APIs implicitly limit methods to objects in particular
abstract states. The ResultSet class of the Java JDBC library
distinguishes between objects that are open or closed, updatable or
not updatable, sensitive or not sensitive, scrollable or not
scrollable, and so on. To use methods that are only available in a
subset of a ResultSet object's states, a programmer must adhere to the
API protocol.

Unfortunately, the restrictions that make up such API protocols are
often buried in multiple locations across API documentation, possibly
across several classes' documentation. The protocol may never be made
explicit, and it can be time consuming to discover and understand it
from prose. This makes it difficult for users to learn how to
interact with a new API, and research indicates that protocol
violations often result not in errors but in unusual runtime behavior.
One study concludes that a single such bug can require days of a
programmer's time, even with expert help. Further, even when there
are resources to teach new users about an API protocol, the protocols
typically are not represented formally. Naturally, informal protocol
representations cannot be used by automatic checkers to ensure
protocol adherence.

These issues motivate the creation of formal models of API protocols.
Unfortunately, discovering the protocols is far from trivial. The
ResultSet class alone can have 33 different abstract states and
approximately 140 methods. Using brute force to identify appropriate
orderings of method calls could perhaps be feasible, but even if we
cared to attempt that, the brute force approach would not be helpful
in identifying multi-object protocols. How would a brute force
approach recognize that Conditions and ReentrantLocks should be
considered together, or that Collection and Iterator should be
considered together?

Problem Statement

It seems clear from the days spent on protocol bugs that programmers
would find it difficult to hand code a formal model of a particular
API's protocol. And with brute force options off the table, it may be
difficult for a programmer to write a program to construct the model
instead. It is therefore desirable to be able to synthesize formal
models of API protocols.

I would like to synthesize deterministic state machines to formally
model API protocols. Each state transition from s1 to s2 would be
associated with the API call that transitions the system from state s1
to state s2. Each state would be associated with the API calls (for
all of the involved classes) that are possible in that state. This
state machine could serve as a guide to programmers attempting to use
an API for the first time, and could also be used in an automatic
checker to identify violations of the protocols.

Spec

Because of the existence of multi-object protocols, it is probably
insufficient to provide the synthesizer with the ability to generate
and run programs. That said, an API is itself the most complete
specification of the API's behavior. If it were feasible, the ideal
would be to use APIs themselves as the only specifications for their
protocols.

Perhaps more realistically, I propose that it may be possible to
provide a body of non-buggy programs as input. The synthesizer could
then make alterations to those programs (and observe the results) to
add constraints. Presumably, this specification would not be written
at the time of use, but would consist of pre-existing API clients
collected for the purpose. These programs would be unlikely to
constitute a complete specification,. Thus, we would allow the
synthesizer to mutate the base programs to construct more input-output
pairs.

> --
>
>

[Wontae Choi]

Hi all,
Attached file is my proposal.
It is about synthesizing Invariant for GUI testing.

Opinions and criticisms are more then well come.

Best,
Wontae Choi

[Edward Lu]

Hello,

Attached is my proposal.

Best,

Edward

--

--

University of California, Berkeley

Bachelors, Computer Science | 2012

Masters, EECS | 2013

C: (408) 568-7371

edward.k.lu@berkeley.edu

[Mangpo Phitchaya Phothilimthana]

Here is mine.

Mangpo

--
 
 

[CUONG ANH NGUYEN]

Hi all,

Here is my proposal.

I'm looking forward to any advice, feedback and questions.

Regards,

Anh Cuong

--
 
 

 

[Dai Bui]

Just resend my homework in case.

Dai

\

[Tikhon Jelvis]

Here's the first homework with my potential problem.

-Tikhon

On Wed, Aug 29, 2012 at 10:45 PM, Dai Bui <da...@eecs.berkeley.edu> wrote:

Just resend my homework in case.

Dai

\

--

--
 
 
<hw1.pdf>

[Rohin Shah]

Here is mine.  It's a little unusual, and I'm not entirely sure if its feasible, but I want to try it anyway.

Rohin

[Ali Sinan Köksal]

Hi everyone,

Here is my submission. We are in an early stage of a potential collaboration, and due to that, the problem statement and specifications are not very clear.

-- ali

On Thu, Aug 30, 2012 at 3:00 AM, Rohin Shah <rohin...@gmail.com> wrote:

Here is mine.  It's a little unusual, and I'm not entirely sure if its feasible, but I want to try it anyway.

Rohin

--
 
 

[Eric Atkinson]

Hello all,

Here's my proposal. It's a little long, and I don't have all the details straight, but it sounds like it could work. Any feedback would be much appreciated.

Eric

[Garvit Juniwal]

Attached is my proposal. Again, it is very vague at this point and I certainly expect changes.

--
 
 

[Nishant Totla]

Attaching a synthesis idea. I'm not sure how accurate or feasible this is, but I might change it later on. Feedback is appreciated.

--
 
 

--
Nishant

[Michael Driscoll]

My proposal is attached. Feedback welcome.

-Michael Driscoll
mbdri...@cs.berkeley.edu

> --
>
>

[Shaon Barman]

Attached.

-Shaon

[Aaron Davidson]

Sorry for lateness! Attached.

[pbailis]

Apologies for the delay. I've been traveling and am still out of the country.

Synthesizing Distributed Coordination and Compensation Protocols

Background

When designing a distributed application, a programmer must decide what consistency model her shared objects require. Models such as linearizability, or atomicity, simplify programming by exposing a consistent view of all objects to all processes at the expense of performance and system availability. Weaker models such as eventual consistency with session guarantees (e.g., read your writes, monotonic writes), are often cheaper but are considerably more difficult to reason about, shifting the burden away from the object system (e.g., the DBMS or ORM) to the programmer.

The use of weak consistency models is often accompanied by a host of ad-hoc "expert" techniques: limited speculation about objects' values (e.g., proceed as if the value of X is 3, without checking the value for X), compensatory logic in the presence of mis-speculation or concurrent updates (e.g., you changed X to 4, so I should roll back my prior computation), and agreement protocols between processes about future modifications (e.g., we all promise not to decrement X value by more than 2, so X shouldn't ever be negative). When do we need to employ these techniques? Can we decide where to place them and which to use automatically, or even decide when weaker consistency is "worthwhile"? These tasks are hard to get right: one Hacker News commenter recently described the process of intelligent conflict resolution as "like getting your wounds reopened and salted with ritualistic regularity" [1].

Problem Statement

For the purposes of this homework, we can consider a subset of the grand challenge of automatically weakening distributed object consistency and appropriately synthesizing coordination/compensation logic. There are really two sub-problems in this challenge, and let's consider the first: weakening distributed object consistency.

Given a program written for atomic consistency, when can we afford not to synchronize operations (or use a cheaper synchronization construct than atomic broadcast)? Implicitly, in an atomic programming model, all modifications to distributed objects are accompanied by a synchronization barrier (which can alternatively be pushed to the read path, or a combination of the two, but consider the write case to start). Using a weaker consistency model would be equivalent to removing some or all of these barriers in the code, or replacing them with cheaper operations. This is inspired by work by Yelick's group on checking for sequential consistency [2], but:

1. We can consider weaker synchronization primitives such as asynchronous broadcast (a la eventual consistency) or causal broadcast (where values are delivered only after their dependencies).

2. We have to consider additional issues like partial failure and higher penalties for synchronization.

We can consider relaxations from other consistency models (strengthening from, say, eventual to sequential, is trivial, but the converse is more difficult) but a reasonable starting point is atomic consistency.

In terms of code, we're effectively considering placing some form of synchronization construct before and after every object access.

Specification

Note: I do wonder whether the real problem here is in deriving a correct specification rather than synthesizing the correct consistency model. The set of programs that can be automatically weakened without compensation logic is likely small (and trivial). Moreover, actually specifying the class of consistency anomalies that are admissible in a given program is an onerous task requiring a large degree of application- and domain-specific knowledge. Mining a specification may be possible using interactive techniques (e.g., I show you a violation and you tell me if it should be allowed). Otherwise, my fear is that one cannot easily weaken a program written for a stronger consistency model. But let's nonetheless consider how this might work.

As input to the synthesizer, in the atomic weakening case, we can simply provide input traces of distributed program execution according to real-time. It's likely that this will overly constrain us, so we could provide a weaker correctness condition like equivalence of input/output pairs (i.e., corresponds to some linearizable (or sequential) execution) or confluence (i.e., all possible executions produce the same result). Given a set of specifications, one could determine what each consistency model "costs" in terms of synchronization overhead (e.g., confluence requires 2 atomic broadcasts, while equivalent input/ouput requires 8 causal broadcasts). The placement of different barriers by the synthesizer will likely indicate logic that is "unsafe" in a distributed setting, and a user could add some of these ad-hoc synchronization recipes (from the "Background" section) and iterate. This second step could be automated, addressing the second sub-problem of our grand challenge.

[1] http://news.ycombinator.com/item?id=4472172

[2] http://www.cs.berkeley.edu/~kamil/papers/sc05.pdf

[Ras Bodik]

Hi Nishant,

 

I want to follow up on our discussion of HW1 from last week.  Let me know when/if you want to talk further about what direction you want take.

 

You may want to review the proposals submitted by other students, both for inspiration and also to see if you want to join someone to form a team.  Two proposals that are intellectually challenging and could also lead to interesting implementations are by Driscoll and Bailis.

 

Re the meeting on Monday, are you free at 10:30?

 

--Ras

 

 

--
 
 

[Ras Bodik]

You may want to review the proposals submitted by other students, both for inspiration and also to see if you want to join someone to form a team.  Two proposals that are intellectually challenging and could also lead to interesting implementations are by Driscoll and Bailis.

 

This was not meant to say that other proposals are not intellectually challenging.  I just knew these proposals might be of interest to Nishant.  (Sorry, this email was intended to Nishant).

 

--Ras

 

Re the meeting on Monday, are you free at 10:30?

 

--Ras

 

 

From: cs294-s...@googlegroups.com [mailto:cs294-s...@googlegroups.com] On Behalf Of Nishant Totla
Sent: Thursday, August 30, 2012 9:55 AM
To: cs294-s...@googlegroups.com
Subject: Re: Homework 1

 

Attaching a synthesis idea. I'm not sure how accurate or feasible this is, but I might change it later on. Feedback is appreciated.

--